제출 #516179

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516179		Ronin13	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	474 ms	134500 KiB

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 / 100