# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1019162 | blackslex | Monkey and Apple-trees (IZhO12_apple) | C++17 | 408 ms | 232560 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;
int q, rc, x, y, c;
struct node {
int val;
bool lz;
node *l, *r;
node() : val(val), l(nullptr), r(nullptr) {}
node(int val) : val(val), l(nullptr), r(nullptr) {}
};
typedef node* pnode;
pnode rt = nullptr;
void push (int l, int r, pnode &cur) {
if (!cur->lz) return;
cur->val = r - l + 1;
if (l < r) {
if (!cur->l) cur->l = new node();
if (!cur->r) cur->r = new node();
cur->l->lz = cur->r->lz = 1;
}
cur->lz = 0;
}
void upd (int l, int r, pnode &cur, int tl, int tr) {
if (!cur) cur = new node();
push(l, r, cur);
if (l > tr || r < tl) return;
if (l >= tl && r <= tr) return cur->lz = 1, push(l, r, cur), void();
int mid = (l + r) >> 1;
upd(l, mid, cur->l, tl, tr);
upd(mid + 1, r, cur->r, tl, tr);
cur->val = (cur->l ? cur->l->val : 0) + (cur->r ? cur->r->val : 0);
}
int qr (int l, int r, pnode cur, int tl, int tr) {
if (l > tr || r < tl || !cur) return 0;
push(l, r, cur);
if (l >= tl && r <= tr) return cur->val;
int mid = (l + r) >> 1;
return qr(l, mid, cur->l, tl, tr) + qr(mid + 1, r, cur->r, tl, tr);
}
int main() {
scanf("%d", &q);
while (q--) {
scanf("%d %d %d", &rc, &x, &y);
if (rc == 2) upd(-1e9, 1e9, rt, x + c, y + c);
else printf("%d\n", c = qr(-1e9, 1e9, rt, x + c, y + c));
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |