제출 #1282754

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

apple

#include <iostream>
using namespace std;
#define endl '\n'
using ll = int;
struct node{
    ll l,r,sum,mod;
};
ll all;
node t[7000007];
ll newnode(){
    t[++all] = {-1,-1,0,0};
    return all;
}
void push(ll v,ll l,ll r){
    if(l==r) return;
    if(t[v].l==-1) t[v].l = newnode();
    if(t[v].r==-1) t[v].r = newnode();
    ll m = (l+r)>>1;
    if(t[v].mod==1){
        t[t[v].l].sum = m-l+1;
        t[t[v].r].sum = r-m;
    }
    t[t[v].l].mod = max(t[t[v].l].mod,t[v].mod);
    t[t[v].r].mod = max(t[t[v].r].mod,t[v].mod);
    t[v].mod = 0;
    t[v].sum = t[t[v].l].sum+t[t[v].r].sum;
}
void update(ll v,ll tl,ll tr,ll l,ll r){
    if(l>tr||r<tl) return;
    push(v,tl,tr);
    if(tl>=l&&tr<=r) {
        t[v].sum = tr-tl+1;
        t[v].mod = 1;
        return;
    }
    if(t[v].l==-1) t[v].l = newnode();
    if(t[v].r==-1) t[v].r = newnode();
    ll tm = (tl+tr)>>1;
    update(t[v].l,tl,tm,l,r);
    update(t[v].r,tm+1,tr,l,r);
    t[v].sum = t[t[v].l].sum+t[t[v].r].sum;
}
ll get1(ll v,ll tl,ll tr,ll l,ll r){
    if(v==-1||l>tr||r<tl) return 0;
    push(v,tl,tr);
    if(tl>=l&&tr<=r) return t[v].sum;
    ll tm = (tl+tr)>>1;
    return get1(t[v].l,tl,tm,l,r)+get1(t[v].r,tm+1,tr,l,r);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll n,i;
    cin>>n;
    ll root = newnode();
    ll c = 0;
    for(i=1;i<=n;i++){
        ll type,l,r;
        cin>>type>>l>>r;
        if(type==2){
            update(root,1,1e9+1,l+c,r+c);
        }
        else{
            ll rt = get1(root,1,1e9+1,l+c,r+c);
            cout<<rt<<endl;
            c = rt;
        }
    }
    return 0;
}

• Subtask 1: 100 / 100