Submission #1000927

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000927	2024-06-18T11:25:50 Z	ayankarimova	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	291 ms	261712 KB

apple

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=4*6e6+6;
const ll mod=1e9+7;
ll st[sz], le[sz], re[sz], nxt=1, lazy[sz];
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, 1e9, 1, a, b);
        }
        else{
            a+=c; b+=c;
            ll ans=res(1, 1e9, 1, a, b);
            cout<<ans<<endl;
            c=ans;
        }
    }
}
/*
{}[]
*/

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2396 KB	Output is correct
2	Correct	0 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	9 ms	9416 KB	Output is correct
5	Correct	10 ms	10076 KB	Output is correct
6	Correct	10 ms	9820 KB	Output is correct
7	Correct	10 ms	10000 KB	Output is correct
8	Correct	79 ms	54868 KB	Output is correct
9	Correct	173 ms	88640 KB	Output is correct
10	Correct	164 ms	99332 KB	Output is correct
11	Correct	175 ms	107604 KB	Output is correct
12	Correct	184 ms	111308 KB	Output is correct
13	Correct	164 ms	138064 KB	Output is correct
14	Correct	152 ms	139600 KB	Output is correct
15	Correct	264 ms	253660 KB	Output is correct
16	Correct	262 ms	255680 KB	Output is correct
17	Correct	164 ms	144464 KB	Output is correct
18	Correct	155 ms	144468 KB	Output is correct
19	Correct	291 ms	261576 KB	Output is correct
20	Correct	289 ms	261712 KB	Output is correct