# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
941520 | ifateen | Monkey and Apple-trees (IZhO12_apple) | C++14 | 211 ms | 133580 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;
#define mid ((tl + tr) >> 1)
const int MAXN = 1e5 + 3e4;
struct Node {
int sum = 0;
bool lazy_set = false;
int l = 0, r = 0;
} tree[64 * MAXN];
int ptr = 2;
int newchild() {
return ptr++;
}
void propagate(int tl, int tr, int node) {
if (tree[node].lazy_set) {
tree[node].sum = tr - tl + 1;
if (tl == tr) {
tree[node].lazy_set = false;
return;
}
if (!tree[node].l) tree[node].l = newchild();
if (!tree[node].r) tree[node].r = newchild();
tree[tree[node].l].lazy_set = true;
tree[tree[node].r].lazy_set = true;
}
tree[node].lazy_set = false;
}
void update(int tl, int tr, int node, int l, int r) {
propagate(tl, tr, node);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
tree[node].lazy_set = true;
propagate(tl, tr, node);
return;
}
if (!tree[node].l) tree[node].l = newchild();
if (!tree[node].r) tree[node].r = newchild();
update(tl, mid, tree[node].l, l, r);
update(mid + 1, tr, tree[node].r, l, r);
tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
}
int query(int tl, int tr, int node, int l, int r) {
propagate(tl, tr, node);
if (tl > r || tr < l) return 0;
if (tl >= l && tr <= r) {
return tree[node].sum;
}
int ret = 0;
if (tree[node].l) ret += query(tl, mid, tree[node].l, l, r);
if (tree[node].r) ret += query(mid + 1, tr, tree[node].r, l, r);
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
for (auto& i : tree) i.l = 0, i.r = 0, i.sum = 0, i.lazy_set = false;
int q;
cin >> q;
int c = 0;
while (q--) {
int t, l, r;
cin >> t >> l >> r;
l += c, r += c;
if (t == 1) cout << (c = query(1, 1'000'000'000, 1, l, r)) << '\n';
else update(1, 1'000'000'000, 1, l, r);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |