Submission #1000923

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1000923	2024-06-18T11:24:34 Z	ayankarimova	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	262144 KB

apple

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	1 ms	2396 KB	Output is correct
4	Correct	8 ms	9564 KB	Output is correct
5	Correct	9 ms	10076 KB	Output is correct
6	Correct	9 ms	9820 KB	Output is correct
7	Correct	9 ms	10124 KB	Output is correct
8	Correct	75 ms	54868 KB	Output is correct
9	Correct	170 ms	88656 KB	Output is correct
10	Correct	173 ms	99424 KB	Output is correct
11	Correct	170 ms	107684 KB	Output is correct
12	Correct	182 ms	111440 KB	Output is correct
13	Correct	161 ms	138332 KB	Output is correct
14	Correct	158 ms	139604 KB	Output is correct
15	Execution timed out	2328 ms	262144 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-