답안 #1100155

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1100155	2024-10-13T02:59:28 Z	spycoderyt	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	498 ms	208864 KB

apple

#include <bits/stdc++.h>
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;
int 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

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	20 ms	4956 KB	Output is correct
5	Correct	24 ms	5808 KB	Output is correct
6	Correct	21 ms	5724 KB	Output is correct
7	Correct	23 ms	5968 KB	Output is correct
8	Correct	155 ms	44256 KB	Output is correct
9	Correct	312 ms	76728 KB	Output is correct
10	Correct	333 ms	84568 KB	Output is correct
11	Correct	300 ms	90964 KB	Output is correct
12	Correct	304 ms	93776 KB	Output is correct
13	Correct	302 ms	108624 KB	Output is correct
14	Correct	304 ms	109604 KB	Output is correct
15	Correct	428 ms	202832 KB	Output is correct
16	Correct	439 ms	204116 KB	Output is correct
17	Correct	341 ms	115280 KB	Output is correct
18	Correct	414 ms	115280 KB	Output is correct
19	Correct	487 ms	208864 KB	Output is correct
20	Correct	498 ms	208728 KB	Output is correct