Submission #1015604

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1015604	2024-07-06T15:03:45 Z	dpsaveslives	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	213 ms	188656 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	185936 KB	Output is correct
2	Correct	53 ms	185768 KB	Output is correct
3	Correct	53 ms	185896 KB	Output is correct
4	Correct	58 ms	185936 KB	Output is correct
5	Correct	63 ms	185944 KB	Output is correct
6	Correct	60 ms	185936 KB	Output is correct
7	Correct	62 ms	185936 KB	Output is correct
8	Correct	104 ms	186852 KB	Output is correct
9	Correct	166 ms	187988 KB	Output is correct
10	Correct	176 ms	187984 KB	Output is correct
11	Correct	169 ms	187984 KB	Output is correct
12	Correct	173 ms	187984 KB	Output is correct
13	Correct	161 ms	188556 KB	Output is correct
14	Correct	159 ms	188504 KB	Output is correct
15	Correct	211 ms	188564 KB	Output is correct
16	Correct	213 ms	188544 KB	Output is correct
17	Correct	165 ms	188500 KB	Output is correct
18	Correct	171 ms	188496 KB	Output is correct
19	Correct	212 ms	188516 KB	Output is correct
20	Correct	203 ms	188656 KB	Output is correct