Submission #757181

#TimeUsernameProblemLanguageResultExecution timeMemory
757181tcmmichaelb139Monkey and Apple-trees (IZhO12_apple)C++17
0 / 100
488 ms262144 KiB
#include "bits/stdc++.h" using namespace std; struct Node { long long val; long long lzAdd; long long L, R; Node *c[2]; Node(long long l, long long r) : L(l), R(r) { val = 0; lzAdd = 0; c[0] = c[1] = NULL; } void push() { if (lzAdd == 0) return; val = (R - L + 1) * lzAdd; if (L != R) { if (c[0]) c[0]->lzAdd = lzAdd; if (c[1]) c[1]->lzAdd = lzAdd; } lzAdd = 0; } void extend() { if (!c[0] && !c[1] && L != R) { long long M = (L + R) / 2; c[0] = new Node(L, M); c[1] = new Node(M + 1, R); } } void pull() { val = c[0]->val + c[1]->val; } void upd(long long lo, long long hi, long long inc) { extend(); push(); if (lo > R || L > hi) return; if (lo <= L && R <= hi) { lzAdd = inc; push(); return; } c[0]->upd(lo, hi, inc); c[1]->upd(lo, hi, inc); pull(); } long long query(long long lo, long long hi) { extend(); push(); if (lo > R || L > hi) return 0; if (lo <= L && R <= hi) return val; long long 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'001); long long 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...