제출 #919237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
919237		ibrahim001	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	441 ms	121128 KiB

apple

#include "bits/stdc++.h"
#define intt long long
using namespace std;
const intt inf = 1e18;
const int sz = 1e5+5;
int st[sz*80], lz[sz*80], L[sz*80], R[sz*80];
int last=1;
void check(int in){
    if ( !L[in] )   L[in] = ++last;
    if ( !R[in] )   R[in] = ++last;
}
void relax(int l, int r, int in){
    if ( !lz[in] )  return;
    st[in] = (r-l+1);
    if ( l == r ){
        lz[in]=0;
        return;
    }
    check(in);
    lz[L[in]] += lz[in];
    lz[R[in]] += lz[in];
    lz[in]=0;
}
void update(int a, int b, int l, int r, int in){
    relax(l, r, in);
    if ( l > b or r < a )   return;
    if ( a <= l and r <= b ){
        lz[in]++;
        relax(l, r, in);
        // cout << l << " " << r << " : " << st[in] << endl;
        return;
    }
    int mid = (l+r)>>1;
    if ( a > mid ){
        if ( !R[in] )   R[in] = ++last;
        update(a, b, mid+1, r, R[in]);
    }
    else if ( b <= mid ){
        if ( !L[in] )   L[in] = ++last;
        update(a, b, l, mid, L[in]);
    }
    else{
        check(in);
        update(a, b, l, mid, L[in]);
        update(a, b, mid+1, r, R[in]);
    }
    relax(l, mid, L[in]);
    relax(mid+1, r, R[in]);
    st[in] = st[L[in]]+st[R[in]];
    // cout << l << " " << r << " : " << st[in] << endl;
}
int getans(int a, int b, int l, int r, int in){
    relax(l, r, in);
    if ( l > b or r < a )   return 0;
    if ( a <= l and r <= b ){
        // cout << l << " " << r << " : " << st[in] << endl;
        return st[in];
    }
    int mid = (l+r)>>1;
    if ( a > mid ){
        if ( !R[in] )   R[in] = ++last;
        return getans(a, b, mid+1, r, R[in]);
    }
    else if ( b <= mid ){
        if ( !L[in] )   L[in] = ++last;
        return getans(a, b, l, mid, L[in]);
    }
    check(in);
    return getans(a, b, l, mid, L[in])+getans(a, b, mid+1, r, R[in]);
}
int i,j;
signed main(){
    int n=1e9, q;
    cin >> q;
    int c = 0;
    while(q--){
        int t;
        cin >> t;
        int x, y;
        cin >> x >> y;
        x += c;
        y += c;
        if ( t == 1 ){
            int res = getans(x , y, 1, n, 1);
            c = res;
            cout << res << endl;
        }
        else{
            update(x, y, 1, n, 1);
        }
    }
}

• Subtask 1: 100 / 100