제출 #1284911

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

apple

#include <bits/stdc++.h>
using namespace std;

#define pb push_back                    
#define ll long long 
#define s second
#define f first
#define all(v) v.begin(),v.end()
const long long inf = 2e9 + 7;
const int N = 4e6 + 10;
int cur = 0,timer = 1;
int L[N * 3],R[N * 3],t[N * 3];
int d[N * 3];
void push(int u,int l,int r){
   if(d[u] != 0){
       t[u] = r - l + 1;
       if(l != r){
           if(!L[u]) L[u] = ++timer;
           if(!R[u]) R[u] = ++timer;
           d[L[u]] = d[R[u]] = 1;
       }
       d[u] = 0;
   }
}
void upd(int u,int l,int r,int lx,int rx,int x){
    push(u,l,r);
    if(l >= lx && r <= rx){
        d[u] = 1;
        push(u,l,r);
        return;
    }
    else if(l > rx || r < lx) return;
    int mid = (l + r) / 2;
    if(!L[u]) L[u] = ++timer;
    if(!R[u]) R[u] = ++timer;
    upd(L[u],l,mid,lx,rx,x);
    upd(R[u],mid + 1,r,lx,rx,x);
    t[u] = t[L[u]] + t[R[u]];
}
int get(int u,int l,int r,int lx,int rx){
    push(u,l,r);
    if(l >= lx && r <= rx) return t[u];
    else if(l > rx || r < lx) return 0;
    int mid = (l + r) / 2;  
    int ans = 0;
    if(L[u]) ans += get(L[u],l,mid,lx,rx);
    if(R[u]) ans += get(R[u],mid + 1,r,lx,rx);
    return ans;
}
void solve(){
    int n,h = 1e9;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int v,l,r;
        cin >> v >> l >> r;
        if(v == 1){
            int x = get(1,1,h,l + cur,r + cur);
            cur = x;
            cout << x << '\n';
        }
        else{
            upd(1,1,h,l + cur,r + cur,0);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    //freopen("promote.in", "r", stdin);
    //freopen("promote.out", "w", stdout);
    int t1 = 1;
    while(t1--){
     	solve();
    }
}

• Subtask 1: 100 / 100