Submission #516179

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
516179	2022-01-20T14:50:23 Z	Ronin13	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	474 ms	134500 KB

apple

#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define epb emplace_back
#define inf 1e9+1
#define linf 1e18+1
using namespace std;

struct node{
    int sum;
    int lazy;
    int l,r;
    node(){
        sum=0;
        lazy=0;
        l=r=0;
    }
};

vector<node>a;
void make(){
    node x;
    x.l=x.r=0;
    a.pb(x);
}
void push(int v,int l,int r){
    if(a[v].l==0){
        make();
        a[v].l=a.size()-1;
    }
    if(a[v].r==0){
        make();
        a[v].r=a.size()-1;
    }
    if(a[v].lazy==0)return;
    int vl=a[v].l,vr=a[v].r;
    int m=(l+r)/2;
    a[vl].sum=(ll)(m-l+1)*(a[v].lazy);
    a[vr].sum=(ll)(r-m)*a[v].lazy;
    a[vl].lazy=a[vr].lazy=a[v].lazy;
    a[v].lazy=0;
}

void update(int v,int l,int r,int st,int fin){
    if(r<st||l>fin)return;
    if(l>=st&&r<=fin){
        a[v].lazy=1;
        a[v].sum=(r-l+1);
        return;
    }
    int m=(l+r)/2;
    push(v,l,r);
    int vl=a[v].l,vr=a[v].r;
    update(vl,l,m,st,fin);
    update(vr,m+1,r,st,fin);
    a[v].sum=a[vr].sum+a[vl].sum;
}

int get(int v,int l,int r,int st,int fin){
    if(r<st||l>fin)return 0;
    if(l>=st&&r<=fin){
        return a[v].sum;
    }
    int m=(l+r)/2;
    push(v,l,r);
    int vl=a[v].l,vr=a[v].r;
    return get(vl,l,m,st,fin)+
            get(vr,m+1,r,st,fin);
}

int main(){
    int q;cin>>q;
    node root;
    a.pb(root);
    a.pb(root);
    int c=0;
    while(q--){
        int type;cin>>type;
        int x,y;cin>>x>>y;
        if(type==2){
            int l=x+c,r=y+c;
            update(1,1,inf,l,r);
        }
        else{
           int l=x+c,r=y+c;
            c=get(1,1,inf,l,r);
            cout<<c<<"\n";
        }
    }
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	19 ms	2592 KB	Output is correct
5	Correct	25 ms	2588 KB	Output is correct
6	Correct	32 ms	2624 KB	Output is correct
7	Correct	24 ms	2584 KB	Output is correct
8	Correct	158 ms	17504 KB	Output is correct
9	Correct	348 ms	34500 KB	Output is correct
10	Correct	362 ms	34368 KB	Output is correct
11	Correct	474 ms	34332 KB	Output is correct
12	Correct	319 ms	34420 KB	Output is correct
13	Correct	321 ms	68444 KB	Output is correct
14	Correct	315 ms	68436 KB	Output is correct
15	Correct	415 ms	134304 KB	Output is correct
16	Correct	411 ms	134500 KB	Output is correct
17	Correct	323 ms	68432 KB	Output is correct
18	Correct	322 ms	68692 KB	Output is correct
19	Correct	412 ms	134308 KB	Output is correct
20	Correct	439 ms	134388 KB	Output is correct