Submission #1015604

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015604		dpsaveslives	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	213 ms	188656 KiB

apple

#include <bits/stdc++.h>
using namespace std;

struct Node{
    int sum,lazy,tl,tr,l,r;
    Node(): sum(0), lazy(0), l(-1), r(-1) {}
};

const int MAXN = 123456;
const int INF = 1e9;
Node segtree[64*MAXN];
int cnt = 2;
void push(int p){
    if(segtree[p].lazy){
        int mid = (segtree[p].tl+segtree[p].tr)>>1;
        segtree[p].sum = segtree[p].tr-segtree[p].tl+1;
        if(segtree[p].l == -1){
            segtree[p].l = cnt++;
            segtree[segtree[p].l].tl = segtree[p].tl;
            segtree[segtree[p].l].tr = mid;
        }
        if(segtree[p].r == -1){
            segtree[p].r = cnt++;
            segtree[segtree[p].r].tl = mid+1;
            segtree[segtree[p].r].tr = segtree[p].tr;
        }
        segtree[segtree[p].r].lazy = segtree[segtree[p].l].lazy = 1;
        segtree[p].lazy = 0;
    }
}
void upd(int l, int r, int p){
    push(p);

    if(l == segtree[p].tl && r == segtree[p].tr){
        segtree[p].lazy = 1;
        push(p);
    }
    else{
        int mid = (segtree[p].tl+segtree[p].tr)>>1;
        if(segtree[p].l == -1){
            segtree[p].l = cnt++;
            segtree[segtree[p].l].tl = segtree[p].tl;
            segtree[segtree[p].l].tr = mid;
        }
        if(segtree[p].r == -1){
            segtree[p].r = cnt++;
            segtree[segtree[p].r].tl = mid+1;
            segtree[segtree[p].r].tr = segtree[p].tr;
        }
        if(l > mid){
            upd(l,r,segtree[p].r);
        }
        else if(r <= mid){
            upd(l,r,segtree[p].l);
        }
        else{
            upd(l,mid,segtree[p].l);
            upd(mid+1,r,segtree[p].r);
        }
        push(segtree[p].l);
        push(segtree[p].r);
        segtree[p].sum = segtree[segtree[p].l].sum+segtree[segtree[p].r].sum;
    }
}
int query(int l, int r, int p){
    push(p);
    if(l == segtree[p].tl && r == segtree[p].tr){
        return segtree[p].sum;
    }
    int mid = (segtree[p].tl+segtree[p].tr)>>1;
    if(segtree[p].l == -1){
        segtree[p].l = cnt++;
        segtree[segtree[p].l].tl = segtree[p].tl;
        segtree[segtree[p].l].tr = mid;
    }
    if(segtree[p].r == -1){
        segtree[p].r = cnt++;
        segtree[segtree[p].r].tl = mid+1;
        segtree[segtree[p].r].tr = segtree[p].tr;
    }
    if(l > mid){
        return query(l,r,segtree[p].r);
    }
    if(r <= mid){
        return query(l,r,segtree[p].l);
    }
    return query(l,mid,segtree[p].l)+query(mid+1,r,segtree[p].r);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int M; cin >> M; //number of queries
    segtree[1].tl = 1; segtree[1].tr = INF;
    segtree[1].sum = segtree[1].lazy = 0;
    int C = 0;
    while(M--){
        int op; cin >> op;
        if(op == 2){ //update
            int l,r; cin >> l >> r; //set each of these to 1
            l += C; r += C;
            upd(l,r,1);
        }
        else{ //query
            int l,r; cin >> l >> r; //query on this range
            l += C; r += C;
            C = query(l,r,1);
            cout << C << "\n";
        }
    }
    return 0;
}

• Subtask 1: 100 / 100