Submission #1100154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1100154	2024-10-13T02:58:18 Z	spycoderyt	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	423 ms	262144 KB

apple

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

class tree{
    // keeps the god
    struct node{
        node* l = nullptr;
        node* r = nullptr;
        int val=0,lz=0;
    };
    typedef node* pnode;
    public:
    pnode rt = nullptr;
    void upd(pnode& t,int l,int r) {
        if(t->lz) {
            if(!t->l)t->l = new node();
            if(!t->r)t->r = new node();
            t->val = r - l + 1;
            t->l->lz = t->r->lz = 1;
        }
    }
    int query(pnode& t,int l,int r,int ll,int rr) {
        if(l > r || r < ll || l > rr) return 0;
        if(!t) t = new node();
        upd(t,l,r);
        if(l>=ll&&r<=rr) return t->val;
        int mid = l + (r-l)/2;
        return query(t->l,l,mid,ll,rr) + query(t->r,mid+1,r,ll,rr);
    }
    void upd(pnode& t,int l,int r,int ll,int rr) {
        if(l > r || r < ll || l > rr) return;
        if(!t) t = new node();
        upd(t,l,r);
        if(l>=ll&&r<=rr){
            t->lz=1;
            upd(t,l,r);
            return;
        }
        int mid = l + (r-l)/2;
        upd(t->l,l,mid,ll,rr);
        upd(t->r,mid+1,r,ll,rr);
        t->val = max(t->val,(t->l?t->l->val:0) + (t->r?t->r->val:0));
    }
}t;
int32_t main() {
    int q,a,b,c,val=0;cin>>q;
    while(q--) {
        cin>>a>>b>>c;
        if(a==1) {
            val = t.query(t.rt,1,1e9,b+val,c+val);
            cout << val << "\n";
        } else {
            t.upd(t.rt,1,1e9,b+val,c+val);
        }
    }
}
/*

4
2 2 3
1 1 3
2 2 3
1 -1 3

5
2 5 8
2 7 10
1 5 8
1 7 10
1 1 10


2
2 1 10
1 1 100

*/

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	23 ms	7424 KB	Output is correct
5	Correct	25 ms	8788 KB	Output is correct
6	Correct	25 ms	8692 KB	Output is correct
7	Correct	25 ms	8796 KB	Output is correct
8	Correct	164 ms	67028 KB	Output is correct
9	Correct	337 ms	116308 KB	Output is correct
10	Correct	360 ms	128600 KB	Output is correct
11	Correct	332 ms	137812 KB	Output is correct
12	Correct	341 ms	142008 KB	Output is correct
13	Correct	334 ms	164304 KB	Output is correct
14	Correct	327 ms	165972 KB	Output is correct
15	Runtime error	423 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-