Submission #1404044
Source Code Expand
// In the name of God #include <iostream> #include <algorithm> #include <fstream> #include <vector> #include <deque> #include <assert.h> #include <queue> #include <stack> #include <set> #include <map> #include <stdio.h> #include <string.h> #include <utility> #include <math.h> #include <bitset> #include <iomanip> #include <complex> using namespace std; #define rep(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define x first #define y second #define pb push_back #define SZ(x) (int((x).size())) #define ALL(x) (x).begin(), (x).end() template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<typename T> inline bool smin(T &a, const T &b) { return a > b ? a = b : a; } template<typename T> inline bool smax(T &a, const T &b) { return a < b ? a = b : a; } typedef long long LL; const int N = (int) 1e6 + 6, mod = (int) 0; int to_add[N], mark[N], res[N], a[N], b[N], c[N], p[N], add[N]; set<int> q[N]; int main() { ios_base::sync_with_stdio(0); int n; cin >> n; for (int j = 0; j < n; ++j) cin >> a[j] >> b[j]; for (int j = 0; j < n + 1; ++j) cin >> c[j]; sort(c, c + n + 1); for (int j = 0; j < n; ++j) { a[j] = lower_bound(c, c + n + 1, a[j]) - c; b[j] = lower_bound(c, c + n + 1, b[j]) - c; } for (int j = 0; j < n + 1; ++j) p[j]--; for (int j = 0; j < n; ++j) p[a[j]]++; for (int j = 1; j < n + 1; ++j) p[j] += p[j - 1]; for (int j = 0; j < n; ++j) { if (a[j] > b[j]) { q[a[j] - 1].insert(j); } } int init_res = 0; set<pair<int, int>> st; for (int pos = n; pos >= 0; --pos) { for (int j : q[pos]) st.insert(mp(b[j], j)); add[pos] += add[pos + 1]; p[pos] += add[pos]; while (p[pos] < -1) { if (st.size()) { auto cur = *(st.begin()); int l = cur.first; st.erase(cur); if (l > pos) continue; mark[cur.second] = 1; init_res++; to_add[a[cur.second] - 1]++; to_add[pos]--; add[pos]++; p[pos]++; if (l >= 1) { add[l - 1]--; } } else { init_res = -1e9; break; } } } for (int pos = n; pos >= 0; --pos) { to_add[pos] += to_add[pos + 1]; p[pos] += to_add[pos]; } if (init_res >= 0) { res[0] = n - init_res; for (int j = 0; j < n + 1; ++j) q[j].clear(); for (int j = 0; j < n; ++j) if (!mark[j]) { if (b[j] < a[j]) { q[b[j]].insert(j); } } st.clear(); memset(add, 0, sizeof add); for (int pos = 0; pos <= n; ++pos) { res[pos + 1] = res[pos]; for (int j : q[pos]) st.insert(mp(-a[j], j)); if (pos >= 1) add[pos] += add[pos - 1]; p[pos] += add[pos]; while (p[pos] == -1) { if (st.size()) { auto cur = *(st.begin()); int r = -cur.first; st.erase(cur); if (r <= pos) continue; mark[cur.second] = 1; res[pos + 1]--; add[pos]++; p[pos]++; add[r]--; } else { res[pos + 1] = -1e9; break; } } } for (int j = 0; j <= n + 1; ++j) { res[j] = max(res[j], -1); } } else { memset(res, -1, sizeof res); } int qn; cin >> qn; while (qn--) { int x, y; cin >> x >> y; x = lower_bound(c, c + n + 1, x) - c; y = lower_bound(c, c + n + 1, y) - c; int ansx = (res[x] == -1 ? -1 : res[x] + 1); int ansy = (res[y] == -1 ? -1 : res[y]); cout << max(ansx, ansy) << '\n'; } }
Submission Info
Submission Time | |
---|---|
Task | F - Two Faced Cards |
User | Reyna |
Language | C++14 (GCC 5.4.1) |
Score | 2000 |
Code Size | 3593 Byte |
Status | AC |
Exec Time | 361 ms |
Memory | 73728 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 2000 / 2000 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_51.txt, subtask_1_52.txt, subtask_1_53.txt, subtask_1_54.txt, subtask_1_55.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 22 ms | 63744 KB |
sample_02.txt | AC | 22 ms | 63744 KB |
sample_03.txt | AC | 22 ms | 63744 KB |
subtask_1_01.txt | AC | 111 ms | 66688 KB |
subtask_1_02.txt | AC | 178 ms | 68992 KB |
subtask_1_03.txt | AC | 76 ms | 65280 KB |
subtask_1_04.txt | AC | 114 ms | 70144 KB |
subtask_1_05.txt | AC | 158 ms | 66048 KB |
subtask_1_06.txt | AC | 258 ms | 70016 KB |
subtask_1_07.txt | AC | 165 ms | 71552 KB |
subtask_1_08.txt | AC | 165 ms | 70528 KB |
subtask_1_09.txt | AC | 212 ms | 71040 KB |
subtask_1_10.txt | AC | 112 ms | 68608 KB |
subtask_1_11.txt | AC | 98 ms | 66176 KB |
subtask_1_12.txt | AC | 110 ms | 67072 KB |
subtask_1_13.txt | AC | 199 ms | 68352 KB |
subtask_1_14.txt | AC | 88 ms | 67328 KB |
subtask_1_15.txt | AC | 100 ms | 69504 KB |
subtask_1_16.txt | AC | 108 ms | 65152 KB |
subtask_1_17.txt | AC | 333 ms | 73472 KB |
subtask_1_18.txt | AC | 59 ms | 67072 KB |
subtask_1_19.txt | AC | 269 ms | 69120 KB |
subtask_1_20.txt | AC | 219 ms | 70400 KB |
subtask_1_21.txt | AC | 336 ms | 68992 KB |
subtask_1_22.txt | AC | 333 ms | 73728 KB |
subtask_1_23.txt | AC | 338 ms | 68992 KB |
subtask_1_24.txt | AC | 335 ms | 73728 KB |
subtask_1_25.txt | AC | 360 ms | 73728 KB |
subtask_1_26.txt | AC | 333 ms | 73216 KB |
subtask_1_27.txt | AC | 311 ms | 71808 KB |
subtask_1_28.txt | AC | 329 ms | 71296 KB |
subtask_1_29.txt | AC | 357 ms | 73728 KB |
subtask_1_30.txt | AC | 339 ms | 73088 KB |
subtask_1_31.txt | AC | 310 ms | 71808 KB |
subtask_1_32.txt | AC | 333 ms | 71296 KB |
subtask_1_33.txt | AC | 356 ms | 73728 KB |
subtask_1_34.txt | AC | 334 ms | 73088 KB |
subtask_1_35.txt | AC | 312 ms | 71296 KB |
subtask_1_36.txt | AC | 322 ms | 71296 KB |
subtask_1_37.txt | AC | 350 ms | 73728 KB |
subtask_1_38.txt | AC | 329 ms | 73088 KB |
subtask_1_39.txt | AC | 315 ms | 72704 KB |
subtask_1_40.txt | AC | 333 ms | 71296 KB |
subtask_1_41.txt | AC | 322 ms | 68992 KB |
subtask_1_42.txt | AC | 273 ms | 65280 KB |
subtask_1_43.txt | AC | 361 ms | 73600 KB |
subtask_1_44.txt | AC | 287 ms | 65664 KB |
subtask_1_45.txt | AC | 275 ms | 67328 KB |
subtask_1_46.txt | AC | 325 ms | 68992 KB |
subtask_1_47.txt | AC | 273 ms | 64384 KB |
subtask_1_48.txt | AC | 359 ms | 72704 KB |
subtask_1_49.txt | AC | 271 ms | 65024 KB |
subtask_1_50.txt | AC | 266 ms | 66688 KB |
subtask_1_51.txt | AC | 22 ms | 61696 KB |
subtask_1_52.txt | AC | 22 ms | 63744 KB |
subtask_1_53.txt | AC | 22 ms | 63744 KB |
subtask_1_54.txt | AC | 21 ms | 61696 KB |
subtask_1_55.txt | AC | 22 ms | 63744 KB |