Submission #1200727

#TimeUsernameProblemLanguageResultExecution timeMemory
1200727GoBananas69Examination (JOI19_examination)C++20
0 / 100
162 ms23336 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; struct Query { int type, s, t, sum, idx; }; struct segment_tree { vector<int> tree; int n; void build(int sz) { tree.resize(4 * sz, 0); n = sz; } void update(int i, int L, int R, int p) { if (L == R) { tree[i]++; return; } int m = (L + R) / 2; int x = 2 * i + 1, y = x + 1; if (p <= m) { update(x, L, m, p); } else { update(y, m + 1, R, p); } tree[i] = tree[x] + tree[y]; } void update(int p) { update(0, 0, n - 1, p); } int query(int i, int L, int R, int l, int r) { if (L == l && r == R) { return tree[i]; } int m = (L + R) / 2; int x = 2 * i + 1, y = x + 1; if (r <= m) { return query(x, L, m, l, r); } else if (l > m) { return query(y, m + 1, R, l, r); } else { int q1 = query(x, L, m, l, m); int q2 = query(y, m + 1, R, m + 1, r); return q1 + q2; } } int query(int l, int r) { return query(0, 0, n - 1, l, r); } } A, B, C; int main() { cin.tie(0) -> sync_with_stdio(0); int n, k; cin >> n >> k; vector<Query> a(n + k); vector<Query> b(n + k); vector<Query> c(n + k); for (int i = 0; i < n; ++i) { int s, t; cin >> s >> t; a[i] = {0, s, t, s + t, -1}; b[i] = {0, s, t, s + t, -1}; c[i] = {0, s, t, s + t, -1}; } for (int i = n; i < n + k; ++i) { int s, t, sum; cin >> s >> t >> sum; a[i] = {1, s, t, sum, i - n}; b[i] = {1, s, t, sum, i - n}; c[i] = {1, s, t, sum, i - n}; } sort(a.begin(), a.end(), [](const Query &x, const Query &y) { if (x.s != y.s) return x.s > y.s; return x.type < y.type; }); sort(b.begin(), b.end(), [](const Query &x, const Query &y) { if (x.t != y.t) return x.t > y.t; return x.type < y.type; }); sort(c.begin(), c.end(), [](const Query &x, const Query &y) { if (x.sum != y.sum) return x.sum > y.sum; return x.type < y.type; }); int sz = 0; for (int i = 0; i < n + k; ++i) { sz = max({sz, a[i].s, b[i].t, c[i].sum}); } A.build(sz + 1); B.build(sz + 1); C.build(sz + 1); vector<int> ac(k), bc(k), cc(k); for (Query &q: a) { if (q.type == 1) { ac[q.idx] = A.query(q.sum, sz); } else { A.update(q.sum); } } for (Query &q: b) { if (q.type == 1) { bc[q.idx] = B.query(q.sum, sz); } else { B.update(q.sum); } } for (Query &q: c) { if (q.type == 1) { cc[q.idx] = C.query(q.sum, sz); } else { C.update(q.sum); } } for (int i = 0; i<k; ++i) { // cout << ac[i] << " + " << bc[i] << " - " << cc[i] << '\n'; cout << ac[i] + bc[i] - cc[i] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...