# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
757216 | tcmmichaelb139 | Monkey and Apple-trees (IZhO12_apple) | C++17 | 1 ms | 212 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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) {
if (c[0]) c[0]->lzAdd = lzAdd;
if (c[1]) c[1]->lzAdd = lzAdd;
}
lzAdd = 0;
}
void upd(int lo, int hi, int 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);
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;
int res = 0;
if (c[0]) res += c[0]->query(lo, hi);
if (c[1]) 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 time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |