Submission #1185973

#TimeUsernameProblemLanguageResultExecution timeMemory
1185973petezaMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
476 ms260456 KiB
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;

struct node {
    int val = 0, laz = 0;
    node *l=0, *r=0;
    node() {}
} *root;

void push(node*&cur, int subcnt) {
    if(!cur->laz) return ;
    cur->val = subcnt; cur->laz = 0;
    if(subcnt > 1) {
        if(!cur->l) cur->l = new node();
        if(!cur->r) cur->r = new node();
        cur->l->laz = 1; cur->r->laz = 1;
    }
}

int qr(node*&cur, int l, int r, int tl, int tr) {
    if(!cur) return 0;
    push(cur, r-l+1);
    if(tl <= l && r <= tr) return cur->val;
    if(tr < l || r < tl) return 0;
    int mid = (l+r) >> 1;
    return qr(cur->l, l, mid, tl, tr) + qr(cur->r, mid+1, r, tl, tr);
}

void upd(node *&cur, int l, int r, int tl, int tr) {
    if(!cur) cur = new node();
    push(cur, r-l+1);
    if(tr < l || r < tl) return;
    if(tl <= l && r <= tr) {
        cur->laz = 1;
        push(cur, r-l+1);
        return ;
    }
    int mid = (l+r) >> 1;
    upd(cur->l, l, mid, tl, tr);
    upd(cur->r, mid+1, r, tl, tr);
    cur->val = (cur->l ? cur->l->val : 0) + (cur->r ? cur->r->val : 0);
}

int m, a, b, c, ccur = 0;

int main() {
    cin >> m;
    while(m--) {
        cin >> a >> b >> c;
        b += ccur; c += ccur;
        if(a == 1) {
            ccur = qr(root, 1, inf, b, c);
            cout << ccur << '\n';
        } else {
            upd(root, 1, inf, b, c);
        }
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...