Submission #1205096

#TimeUsernameProblemLanguageResultExecution timeMemory
1205096GoBananas69Monkey and Apple-trees (IZhO12_apple)C++20
0 / 100
3 ms1352 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; struct Node { Node *l = nullptr, *r = nullptr; ll sum = 0; bool covered = false; Node() = default; void push(ll L, ll R) { if (!covered || L == R) return; ll M = (L + R) >> 1; if (!l) l = new Node(); if (!r) r = new Node(); l->covered = true; l->sum = (M - L + 1); r->covered = true; r->sum = (R - M); covered = false; } void update(ll L, ll R, ll ql, ll qr) { if (qr < L || R < ql) return; if (ql <= L && R <= qr) { covered = true; sum = (R - L + 1); return; } push(L, R); ll M = (L + R) >> 1; if (!l) l = new Node(); if (!r) r = new Node(); l->update(L, M, ql, qr); r->update(M + 1, R, ql, qr); sum = l->sum + r->sum; } ll query(ll L, ll R, ll ql, ll qr) { if (qr < L || R < ql) return 0; if (ql <= L && R <= qr) return sum; push(L, R); ll M = (L + R) >> 1; ll ans = 0; if (l) ans += l->query(L, M, ql, qr); if (r) ans += r->query(M + 1, R, ql, qr); return ans; } ~Node() { delete l; delete r; } }; int main() { cin.tie(0) -> sync_with_stdio(0); int M; cin >> M; const ll N = 200000; Node *root = new Node(); ll C = 0; while (M--) { int D; ll X, Y; cin >> D >> X >> Y; X += C; Y += C; if (X > Y) swap(X, Y); if (D == 2) { root->update(1, N, X, Y); } else { C = root->query(1, N, X, Y); cout << C << "\n"; } } delete root; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...