제출 #1221238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221238		Sofiatpc	원숭이와 사과 나무 (IZhO12_apple)	C++20	0 / 100	0 ms	324 KiB

apple

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAX = 1e9;
vector<int> sum, lz, e, d;

int create(){
    sum.push_back(0);
    lz.push_back(0);
    e.push_back(0);
    d.push_back(0);
    return sz(sum)-1;
}

void refresh(int node, int l, int r){
    if(lz[node] == 0)return;
    sum[node] = (r-l+1)*lz[node];
    if(l != r){
        if(e[node] == 0){
            int aux = create();
            e[node] = aux;
        }
        lz[ e[node] ] = lz[node];

        if(d[node] == 0){
            int aux = create();
            d[node] = aux;
        }
        lz[ d[node] ] = lz[node];
    }
    lz[node] = 0;
}

void update(int node, int l, int r, int i, int j){
    refresh(node,l,r);
    if(j < l || r < i)return;
    if(i <= l && r <= j){
        lz[node] = 1;
        refresh(node,l,r);
        return;
    }

    int mid = (l+r)>>1;
    if(i <= mid){
        if(e[node] == 0){
            int aux = create();
            e[node] = aux;
        }
        update(e[node],l,mid,i,j);
    }

    if(j > mid){
        if(d[node] == 0){
            int aux = create();
            d[node] = aux;
        }
        update(d[node],mid+1,r,i,j);
    }

    refresh(e[node],l,mid); refresh(d[node],mid+1,r);
    sum[node] = sum[e[node]] + sum[d[node]];
}

int query(int node, int l, int r, int i, int j){
    if(node == 0)return 0;
    refresh(node,l,r);
    if(j < l || r < i)return 0;
    if(i <= l && r <= j)return sum[node];

    int mid = (l+r)>>1;
    return query(e[node],l,mid,i,j) + query(d[node],mid+1,r,i,j);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int m; cin>>m;
    create(); create();
    int c = 0;
    for(int i = 1; i <= m; i++){
        int d,x,y; cin>>d>>x>>y;
        if(d == 1){
            int ans = query(1,1,MAX, x+c,y+c);
            c += ans;
            cout<<ans<<"\n";
        }else update(1,1,MAX, x+c,y+c);
    }
}

• Subtask 1: 0 / 100