Submission #593387

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
593387	2022-07-11T03:08:38 Z	karrigan	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	343 ms	200076 KB

apple

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
using namespace std;
struct node{
int l,r,next1,next2;
int lazy,val;
node(){
next1=-1;
next2=-1;
lazy=0;
val=0;
}
};
vector<node>st;
void push(int t){
if (st[t].next1!=-1&&st[t].next2!=-1&&st[t].lazy!=0){
    int l=st[t].l,r=st[t].r;
    int mid=(l+r)/2;
    int lep=st[t].next1,rai=st[t].next2;
    st[lep].val=(mid-l+1);
    st[lep].lazy=1;
    st[rai].val=(r-mid);
    st[rai].lazy=1;
    st[t].lazy=0;
    return;
}
}
void update(int t,int l,int r){
    //cout<<l<<" "<<r<<" "<<st[t].l<<" "<<st[t].r<<'\n';
    if (st[t].l>r||st[t].r<l)return;
    if (l<=st[t].l&&st[t].r<=r){
        st[t].lazy=1;
        st[t].val=(st[t].r-st[t].l+1);
        return;
    }
    int mid=(st[t].l+st[t].r)/2;
    if (st[t].next1==-1&&st[t].next2==-1){
    st[t].next1=st.size();
    node fk;
    fk.l=st[t].l;
    fk.r=mid;
    st.push_back(fk);
    node ff;
    ff.l=mid+1;
    ff.r=st[t].r;
    st[t].next2=st.size();
    st.push_back(ff);
    }
    push(t);
    update(st[t].next1,l,r);
    update(st[t].next2,l,r);
    st[t].val=st[st[t].next1].val+st[st[t].next2].val;
}
int query(int t,int l,int r,int u,int v){
    //cout<<u<<" "<<v<<" "<<st[t].l<<" "<<st[t].r<<" "<<st[t].val<<'\n';
    if (r<u||l>v)return 0;
    if (u<=l&&r<=v)return st[t].val;
   int mid=(st[t].l+st[t].r)/2;
    if (st[t].next1==-1&&st[t].next2==-1){
    st[t].next1=st.size();
    node fk;
    fk.l=st[t].l;
    fk.r=mid;
    st.push_back(fk);
    node ff;
    ff.l=mid+1;
    ff.r=st[t].r;
    st[t].next2=st.size();
    st.push_back(ff);
    }
    push(t);
    long long ans=query(st[t].next1,l,mid,u,v)+query(st[t].next2,mid+1,r,u,v);
    st[t].val=st[st[t].next1].val+st[st[t].next2].val;
    return ans;
}
int main()
{
    fastio
    //freopen(".INP","r",stdin);
    //freopen(".OUT","w",stdout);
    int m;
    cin>>m;
    node temp;
    temp.l=1;
    temp.r=1e9;
    st.push_back(temp);
    int c=0;
    for (int i=1;i<=m;i++){
       int z,x,y;
       cin>>z>>x>>y;
       x+=c;
       y+=c;
       if (z==1){
        c=query(0,1,1000000000,x,y);
        cout<<c<<'\n';
       }
       else {
        update(0,x,y);
       }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	11 ms	3652 KB	Output is correct
5	Correct	13 ms	3648 KB	Output is correct
6	Correct	13 ms	3656 KB	Output is correct
7	Correct	14 ms	3656 KB	Output is correct
8	Correct	98 ms	25696 KB	Output is correct
9	Correct	211 ms	50564 KB	Output is correct
10	Correct	204 ms	50640 KB	Output is correct
11	Correct	208 ms	50564 KB	Output is correct
12	Correct	218 ms	50796 KB	Output is correct
13	Correct	217 ms	100044 KB	Output is correct
14	Correct	217 ms	100100 KB	Output is correct
15	Correct	343 ms	200076 KB	Output is correct
16	Correct	333 ms	200056 KB	Output is correct
17	Correct	244 ms	101372 KB	Output is correct
18	Correct	222 ms	101392 KB	Output is correct
19	Correct	332 ms	200016 KB	Output is correct
20	Correct	330 ms	200000 KB	Output is correct