제출 #496388

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

apple

#include <bits/stdc++.h>

using namespace std;

typedef int ll;

const ll Size=1e7+7;
pair<ll,ll> seg_tree[4*Size];

void update(ll l,ll r,ll i,ll tl,ll tr){
    if(tl>r or tr<l)return;
    if(tl==l and tr==r){
        seg_tree[i].second++;
        seg_tree[i].first+=r-l+1;
    }else{
        ll mid=(l+r)/2;
        update(l,mid,i*2,tl,min(mid,tr));
        update(mid+1,r,i*2+1,max(mid+1,tl),tr);
        seg_tree[i].first=seg_tree[i*2].first+seg_tree[i*2+1].first;
    }
}

ll query(ll l,ll r,ll i,ll tl,ll tr){
    if(tl>r or tr<l)return -1;
    if(tl==l and tr==r){
        return seg_tree[i].first;
    }else{
        ll mid=(l+r)/2;
        ll n1=query(l,mid,i*2,tl,min(mid,tr));
        ll n2=query(mid+1,r,i*2+1,max(mid+1,tl),tr);
        if(n1==-1)return n2;
        if(n2==-1)return n1;
        return n1+n2;
    }
}

void solve(){
    ll m,c=0;
    cin>>m;
    for(ll i=0;i<m;i++){
        ll d,x,y;
        cin>>d>>x>>y;
        if(d==1){
            update(1,1e7,1,x+c,y+c);
        }
        if(d==2){
            c+=query(1,1e7,1,x+c,y+c);
        }
    }
    cout<<c<<endl;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    while(t--){
        solve();
    }
    return 0;
}

• Subtask 1: 0 / 100