Submission #534903
Source Code Expand
#include <vector> #include <iostream> #include <algorithm> #include <set> #include <map> #include <queue> #include <cmath> using namespace std; typedef long long li; typedef long double real; #define rep(i, n) for(int i = 0; i < (int)(n); ++i) const li bit_max = 1e5 + 10; li bit[bit_max + 1]; li sum(int i) { li s = 0; while (i > 0) { s += bit[i]; i -= i & -i; } return s; } void add(int i, li x) { while (i <= bit_max) { bit[i] += x; i += i & -i; } } int main() { li n; cin >> n; vector<li> a(n), b(n); rep(i, n) { cin >> a[i]; } rep(i, n) { cin >> b[i]; } priority_queue<pair<li, li>> q; rep(i, n) { q.emplace(a[i], i); } li ans = 0; priority_queue<int> cands; for (li i = n-1; i >= 0; --i) { while (not q.empty() && q.top().first >= b[i]) { cands.emplace(q.top().second); //cerr << "ins " << q.top().second << endl; q.pop(); } if (cands.empty()) { cout << -1 << endl; return 0; } ans += i - cands.top() + sum(cands.top() + 1); add(cands.top() + 1, 1); //cerr << "out " << cands.top() << ", ans = " << ans << endl; cands.pop(); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | G - ケンドー |
User | amylase |
Language | C++11 (GCC 4.9.2) |
Score | 300 |
Code Size | 1405 Byte |
Status | AC |
Exec Time | 221 ms |
Memory | 5524 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 | 28 ms | 924 KB |
00_small_sample_01.txt | AC | 27 ms | 800 KB |
00_small_sample_02.txt | AC | 27 ms | 928 KB |
10_small_01.txt | AC | 26 ms | 800 KB |
10_small_02.txt | AC | 28 ms | 800 KB |
10_small_03.txt | AC | 28 ms | 796 KB |
10_small_04.txt | AC | 26 ms | 796 KB |
10_small_05.txt | AC | 28 ms | 804 KB |
10_small_06.txt | AC | 28 ms | 792 KB |
10_small_07.txt | AC | 27 ms | 792 KB |
10_small_08.txt | AC | 28 ms | 800 KB |
10_small_09.txt | AC | 26 ms | 796 KB |
10_small_10.txt | AC | 27 ms | 856 KB |
20_large_01.txt | AC | 202 ms | 5264 KB |
20_large_02.txt | AC | 201 ms | 5264 KB |
20_large_03.txt | AC | 208 ms | 5396 KB |
20_large_04.txt | AC | 214 ms | 5516 KB |
20_large_05.txt | AC | 208 ms | 5388 KB |
20_large_06.txt | AC | 208 ms | 5392 KB |
20_large_07.txt | AC | 197 ms | 5136 KB |
20_large_08.txt | AC | 209 ms | 5324 KB |
20_large_09.txt | AC | 215 ms | 5524 KB |
20_large_10.txt | AC | 202 ms | 5200 KB |
30_maxcase_01.txt | AC | 159 ms | 4756 KB |
31_almost_maxcase_01.txt | AC | 200 ms | 4752 KB |
31_almost_maxcase_02.txt | AC | 194 ms | 4624 KB |
31_almost_maxcase_03.txt | AC | 198 ms | 4752 KB |
31_almost_maxcase_04.txt | AC | 197 ms | 4760 KB |
31_almost_maxcase_05.txt | AC | 209 ms | 4760 KB |
40_bad_maxcase_01.txt | AC | 185 ms | 4376 KB |
40_bad_maxcase_02.txt | AC | 174 ms | 4448 KB |
40_bad_maxcase_03.txt | AC | 221 ms | 4816 KB |
40_bad_maxcase_04.txt | AC | 175 ms | 4376 KB |
40_bad_maxcase_05.txt | AC | 194 ms | 4624 KB |
41_bad_shufflecase_01.txt | AC | 185 ms | 4756 KB |
41_bad_shufflecase_02.txt | AC | 194 ms | 4624 KB |
41_bad_shufflecase_03.txt | AC | 188 ms | 4752 KB |
41_bad_shufflecase_04.txt | AC | 179 ms | 4680 KB |