Submission #534800
Source Code Expand
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
using namespace std;
class SegmentTree
{
private:
typedef int T1;
typedef int T2;
// データの初期値、以下の条件を満たすこと
// uniteData(v, INIT_DATA) == v
const T1 INIT_DATA = 0;
// 遅延の初期値、以下の条件を満たすこと
// updateData(prev, size, INIT_DELAY) == prev
// updateDelay(x, INIT_DELAY) == x
const T2 INIT_DELAY = 0;
// 長さがsizeの区間における前回の計算結果prevに対して、
// 区間の各要素にパラメータxを用いた更新処理を適用した後の計算結果を返す
T1 updateData(T1 prev, int size, T2 x){
return prev + x * size;
}
// パラメータx1,x2による2つの更新処理を順に適用した場合に対して、
// 同じ結果になるような1つの更新処理のパラメータを返す
T2 updateDelay(T2 x1, T2 x2){
return x1 + x2;
}
// 2つの区間の計算結果v1,v2に対して、
// その2つの区間を統合した区間における計算結果を返す
T1 uniteData(T1 v1, T1 v2){
return v1 + v2;
}
int n;
vector<T1> data;
vector<T2> delay;
void updateTree(int a, int b, int k, int l, int r, T2 x){
if(a <= l && r <= b){
data[k] = updateData(data[k], r - l + 1, x);
delay[k] = updateDelay(delay[k], x);
}
else if(a <= r && l <= b){
for(int i=0; i<2; ++i){
data[k*2+1+i] = updateData(data[k*2+1+i], (r - l + 1) / 2, delay[k]);
delay[k*2+1+i] = updateDelay(delay[k*2+1+i], delay[k]);
}
delay[k] = INIT_DELAY;
updateTree(a, b, k*2+1, l, (l+r)/2, x);
updateTree(a, b, k*2+2, (l+r+1)/2, r, x);
data[k] = uniteData(data[k*2+1], data[k*2+2]);
}
}
T1 getValue(int a, int b, int k, int l, int r){
if(a <= l && r <= b){
return data[k];
}
else if(a <= r && l <= b){
T1 v1 = getValue(a, b, k*2+1, l, (l+r)/2);
T1 v2 = getValue(a, b, k*2+2, (l+r+1)/2, r);
return uniteData(v1, v2);
}
else{
return INIT_DATA;
}
}
public:
SegmentTree(int n0){
n = 1;
while(n < n0)
n *= 2;
data.assign(2*n-1, INIT_DATA);
delay.assign(2*n-1, INIT_DELAY);
}
SegmentTree(const vector<T1>& v) : SegmentTree((int)v.size()){
for(unsigned i=0; i<v.size(); ++i)
data[n-1+i] = v[i];
for(int k=n-2; k>=0; --k)
data[k] = uniteData(data[k*2+1], data[k*2+2]);
}
// 区間[a,b]の要素にパラメータxによる更新処理を適用
void update(int a, int b, T2 x){
updateTree(a, b, 0, 0, n-1, x);
}
// 区間[a,b]の計算結果を返す
T1 get(int a, int b){
updateTree(a, b, 0, 0, n-1, 0);
return getValue(a, b, 0, 0, n-1);
}
};
int main()
{
int n;
cin >> n;
vector<pair<int, int> > a(n);
vector<int> b(n);
for(int i=0; i<n; ++i){
cin >> a[i].first;
a[i].second = i;
}
for(int i=0; i<n; ++i)
cin >> b[i];
sort(a.rbegin(), a.rend());
SegmentTree st(n);
priority_queue<int> pq;
int k = 0;
long long ans = 0;
for(int i=n-1; i>=0; --i){
while(k < n && a[k].first >= b[i]){
pq.push(a[k].second);
++ k;
}
if(pq.size() == 0){
cout << -1 << endl;
return 0;
}
int x = pq.top();
pq.pop();
ans += i - x + st.get(x, x);
st.update(x, n-1, 1);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
G - ケンドー |
User |
mamekin |
Language |
C++11 (GCC 4.9.2) |
Score |
300 |
Code Size |
4205 Byte |
Status |
AC |
Exec Time |
323 ms |
Memory |
4640 KB |
Judge Result
Set Name |
Small |
All |
Score / Max Score |
3 / 3 |
297 / 297 |
Status |
|
|
Set Name |
Test Cases |
Small |
00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt |
All |
00_small_sample_00.txt, 00_small_sample_01.txt, 00_small_sample_02.txt, 10_small_01.txt, 10_small_02.txt, 10_small_03.txt, 10_small_04.txt, 10_small_05.txt, 10_small_06.txt, 10_small_07.txt, 10_small_08.txt, 10_small_09.txt, 10_small_10.txt, 20_large_01.txt, 20_large_02.txt, 20_large_03.txt, 20_large_04.txt, 20_large_05.txt, 20_large_06.txt, 20_large_07.txt, 20_large_08.txt, 20_large_09.txt, 20_large_10.txt, 30_maxcase_01.txt, 31_almost_maxcase_01.txt, 31_almost_maxcase_02.txt, 31_almost_maxcase_03.txt, 31_almost_maxcase_04.txt, 31_almost_maxcase_05.txt, 40_bad_maxcase_01.txt, 40_bad_maxcase_02.txt, 40_bad_maxcase_03.txt, 40_bad_maxcase_04.txt, 40_bad_maxcase_05.txt, 41_bad_shufflecase_01.txt, 41_bad_shufflecase_02.txt, 41_bad_shufflecase_03.txt, 41_bad_shufflecase_04.txt |
Case Name |
Status |
Exec Time |
Memory |
00_small_sample_00.txt |
AC |
29 ms |
836 KB |
00_small_sample_01.txt |
AC |
31 ms |
812 KB |
00_small_sample_02.txt |
AC |
26 ms |
792 KB |
10_small_01.txt |
AC |
29 ms |
796 KB |
10_small_02.txt |
AC |
28 ms |
804 KB |
10_small_03.txt |
AC |
29 ms |
808 KB |
10_small_04.txt |
AC |
29 ms |
800 KB |
10_small_05.txt |
AC |
29 ms |
924 KB |
10_small_06.txt |
AC |
29 ms |
920 KB |
10_small_07.txt |
AC |
28 ms |
804 KB |
10_small_08.txt |
AC |
29 ms |
804 KB |
10_small_09.txt |
AC |
28 ms |
800 KB |
10_small_10.txt |
AC |
27 ms |
916 KB |
20_large_01.txt |
AC |
304 ms |
4504 KB |
20_large_02.txt |
AC |
309 ms |
4504 KB |
20_large_03.txt |
AC |
316 ms |
4640 KB |
20_large_04.txt |
AC |
323 ms |
4628 KB |
20_large_05.txt |
AC |
314 ms |
4504 KB |
20_large_06.txt |
AC |
317 ms |
4504 KB |
20_large_07.txt |
AC |
297 ms |
4512 KB |
20_large_08.txt |
AC |
315 ms |
4628 KB |
20_large_09.txt |
AC |
323 ms |
4640 KB |
20_large_10.txt |
AC |
311 ms |
4516 KB |
30_maxcase_01.txt |
AC |
259 ms |
4000 KB |
31_almost_maxcase_01.txt |
AC |
308 ms |
4004 KB |
31_almost_maxcase_02.txt |
AC |
310 ms |
3868 KB |
31_almost_maxcase_03.txt |
AC |
309 ms |
3996 KB |
31_almost_maxcase_04.txt |
AC |
312 ms |
4004 KB |
31_almost_maxcase_05.txt |
AC |
310 ms |
4004 KB |
40_bad_maxcase_01.txt |
AC |
239 ms |
3876 KB |
40_bad_maxcase_02.txt |
AC |
177 ms |
3876 KB |
40_bad_maxcase_03.txt |
AC |
293 ms |
4004 KB |
40_bad_maxcase_04.txt |
AC |
176 ms |
3868 KB |
40_bad_maxcase_05.txt |
AC |
293 ms |
3952 KB |
41_bad_shufflecase_01.txt |
AC |
209 ms |
4004 KB |
41_bad_shufflecase_02.txt |
AC |
254 ms |
3872 KB |
41_bad_shufflecase_03.txt |
AC |
224 ms |
3996 KB |
41_bad_shufflecase_04.txt |
AC |
186 ms |
3880 KB |