Submission #1000929

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000929	2024-06-18T11:27:38 Z	ayankarimova	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	324 ms	261716 KB

apple

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=4*(2e5+5)*30;
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	2392 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	8 ms	8028 KB	Output is correct
5	Correct	11 ms	8872 KB	Output is correct
6	Correct	13 ms	8540 KB	Output is correct
7	Correct	11 ms	10024 KB	Output is correct
8	Correct	85 ms	52856 KB	Output is correct
9	Correct	175 ms	88628 KB	Output is correct
10	Correct	206 ms	99332 KB	Output is correct
11	Correct	213 ms	107604 KB	Output is correct
12	Correct	205 ms	111332 KB	Output is correct
13	Correct	174 ms	138380 KB	Output is correct
14	Correct	176 ms	139604 KB	Output is correct
15	Correct	300 ms	253620 KB	Output is correct
16	Correct	311 ms	255608 KB	Output is correct
17	Correct	206 ms	144592 KB	Output is correct
18	Correct	191 ms	144572 KB	Output is correct
19	Correct	276 ms	261604 KB	Output is correct
20	Correct	324 ms	261716 KB	Output is correct