Submission #757275

#TimeUsernameProblemLanguageResultExecution timeMemory
757275tcmmichaelb139Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
384 ms262144 KiB
#include "bits/stdc++.h" using namespace std; struct Node { int val; int lzAdd; int L, R; Node *c[2]; Node(int l, int r) : L(l), R(r) { val = 0; lzAdd = 0; c[0] = c[1] = NULL; } void extend() { if (!c[0] && !c[1] && L != R) { int M = (L + R) / 2; c[0] = new Node(L, M); c[1] = new Node(M + 1, R); } } void push() { if (lzAdd == 0) return; val = R - L + 1; if (L != R) { extend(); if (c[0]) c[0]->lzAdd = lzAdd; if (c[1]) c[1]->lzAdd = lzAdd; } } void upd(int lo, int hi, int inc) { push(); if (lo > R || L > hi) return; if (lo <= L && R <= hi) { lzAdd = inc; push(); return; } extend(); c[0]->upd(lo, hi, inc); c[1]->upd(lo, hi, inc); val = c[0]->val + c[1]->val; } int query(int lo, int hi) { push(); if (lo > R || L > hi) return 0; if (lo <= L && R <= hi) return val; extend(); int res = 0; res += c[0]->query(lo, hi); res += c[1]->query(lo, hi); return res; } }; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; Node seg(1, 1'000'000'000); int ans = 0; for (int i = 0; i < n; i++) { int a, b, c; cin >> a >> b >> c; if (a == 1) { ans = seg.query(b + ans, c + ans); cout << ans << '\n'; } else { seg.upd(b + ans, c + ans, 1); } } }
#Verdict Execution timeMemoryGrader output
Fetching results...