답안 #516179

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
516179 2022-01-20T14:50:23 Z Ronin13 원숭이와 사과 나무 (IZhO12_apple) C++14
100 / 100
474 ms 134500 KB
#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";
        }
    }
}
# 결과 실행 시간 메모리 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