Submission #1000952

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000952	2024-06-18T11:49:49 Z	ayankarimova	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	211 ms	133712 KB

apple

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll int
const ll sz=(2e5+5)*30;
const int long n=1e9;
ll st[sz*4], le[sz*4], re[sz*4], nxt=1, lazy[sz*4];
void relax(ll l, ll r, ll in)
{
    if(lazy[in]){
        st[in]=r-l+1;
        if(l!=r){
            if(!le[in]) le[in]=++nxt;
            if(!re[in]) re[in]=++nxt;
            lazy[le[in]]=1;
            lazy[re[in]]=1;
        }
        lazy[in]=0;
    }
}
void update(ll l, ll r, ll in, ll ql, ll qr)
{
    relax(l, r, in);
    if(ql>r || qr<l) return;
    if(ql<=l && r<=qr){
        st[in]=r-l+1;
        if(l!=r){
            if(!le[in]) le[in]=++nxt;
            if(!re[in]) re[in]=++nxt;
            lazy[le[in]]=1;
            lazy[re[in]]=1;
        }
        return;
    }
    ll mid=(l+r)/2;
    if(!le[in]) le[in]=++nxt;
    update(l, mid, le[in], ql, qr);
    if(!re[in]) re[in]=++nxt;
    update(mid+1, r, re[in], ql, qr);
    st[in]=st[le[in]]+st[re[in]];
}
ll res(ll l, ll r, ll in, ll ql, ll qr)
{
    relax(l, r, in);
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr) return st[in];
    ll mid=(l+r)/2;
    ll q1, q2;
    if(le[in]) q1=res(l, mid, le[in], ql, qr);
    else q1=0;
    if(re[in]) q2=res(mid+1, r, re[in], ql, qr);
    else q2=0;
    return q1+q2;
}
int main(){

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll m;
    cin>>m;
    ll c=0;
    while(m--){
        ll t, a, b;
        cin>>t>>a>>b;
        if(t==2){
            a+=c; b+=c;
            update(1, n, 1, a, b);
        }
        else{
            a+=c; b+=c;
            ll ans=res(1, n, 1, a, b);
            cout<<ans<<endl;
            c=ans;
        }
    }
}
/*
{}[]
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	8 ms	5980 KB	Output is correct
5	Correct	10 ms	6236 KB	Output is correct
6	Correct	9 ms	6272 KB	Output is correct
7	Correct	9 ms	6232 KB	Output is correct
8	Correct	69 ms	29912 KB	Output is correct
9	Correct	132 ms	47300 KB	Output is correct
10	Correct	133 ms	52008 KB	Output is correct
11	Correct	135 ms	56144 KB	Output is correct
12	Correct	148 ms	57048 KB	Output is correct
13	Correct	138 ms	71880 KB	Output is correct
14	Correct	124 ms	72272 KB	Output is correct
15	Correct	199 ms	129620 KB	Output is correct
16	Correct	200 ms	130132 KB	Output is correct
17	Correct	128 ms	73552 KB	Output is correct
18	Correct	131 ms	73632 KB	Output is correct
19	Correct	210 ms	133712 KB	Output is correct
20	Correct	211 ms	133524 KB	Output is correct