Submission #1111178

#TimeUsernameProblemLanguageResultExecution timeMemory
1111178adaawfFortune Telling 2 (JOI14_fortune_telling2)C++17
0 / 100
3 ms10832 KiB
#include <bits/stdc++.h> using namespace std; int a[200005], b[200005], c[200005], res[200005], t[2400005], tt[2400005], dd[200005], z = 0; map<int, int> m; vector<pair<int, int>> g[200005]; void update(int v, int tl, int tr, int x, int y) { if (tl == tr) { t[v] = max(t[v], y); return; } int mid = (tl + tr) / 2; if (mid >= x) update(v * 2, tl, mid, x, y); else update(v * 2 + 1, mid + 1, tr, x, y); t[v] = max(t[v * 2], t[v * 2 + 1]); } int sum(int v, int tl, int tr, int l, int r) { if (l > r) return 0; if (tl == l && tr == r) { return t[v]; } int mid = (tl + tr) / 2; return max(sum(v * 2, tl, mid, l, min(r, mid)), sum(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r)); } void update2(int v, int tl, int tr, int x) { if (tl == tr) { tt[v]++; return; } int mid = (tl + tr) / 2; if (mid >= x) update2(v * 2, tl, mid, x); else update2(v * 2 + 1, mid + 1, tr, x); tt[v] = tt[v * 2] + tt[v * 2 + 1]; } int sum2(int v, int tl, int tr, int l, int r) { if (l > r) return 0; if (tl == l && tr == r) { return tt[v]; } int mid = (tl + tr) / 2; return sum2(v * 2, tl, mid, l, min(r, mid)) + sum2(v * 2 + 1, mid + 1, tr, max(l, mid + 1), r); } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector<int> v; int n, q; cin >> n >> q; for (int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; v.push_back(a[i]); v.push_back(b[i]); } for (int i = 1; i <= q; i++) { cin >> c[i]; v.push_back(c[i]); } sort(v.begin(), v.end()); for (int w : v) { if (!m.count(w)) { m[w] = ++z; dd[z] = w; } } for (int i = 1; i <= n; i++) a[i] = m[a[i]], b[i] = m[b[i]]; for (int i = 1; i <= q; i++) { c[i] = m[c[i]]; update(1, 1, z, c[i], i); } for (int i = 1; i <= n; i++) { if (a[i] == b[i]) res[i] = 1; else { if (a[i] < b[i]) { res[i] = 1; swap(a[i], b[i]); } int h = sum(1, 1, z, b[i], a[i] - 1) + 1; g[h].push_back({i, a[i]}); } } for (int i = q; i >= 1; i--) { update2(1, 1, z, c[i]); for (auto w : g[i]) { int h = sum2(1, 1, z, w.second, z); if (h & 1) res[w.first] ^= 1; } } long long int d = 0; for (int i = 1; i <= n; i++) { if (res[i] == 0) d += dd[a[i]]; else d += dd[b[i]]; } cout << d; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...