제출 #1348261

#제출 시각아이디문제언어결과실행 시간메모리
1348261yusif_agalarliMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
331 ms244428 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int sz = 1e5+5;
const int inf = 1e18;

int st[80*sz], lz[80*sz], L[80*sz], R[80*sz];
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 ) {
        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( a > r || b < l )  return;
    if( a <= l && b >= r ) {
        lz[in] = 1;
        relax(l, r, in);
        return;
    }
    int mid = (l + r) >> 1;
    if( mid < a ) {
        if( !R[in] ) R[in] = ++last;
        update(a, b, mid + 1, r, R[in]);
    }
    else if( mid >= b ) {
        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]];
}

int ask(int a, int b, int l, int r, int in) {
    relax(l, r, in);
    if( a > r || b < l ) return 0;
    if( a <= l && b >= r ) return st[in];
    int mid = (l + r) >> 1;
    if( mid < l ) {
        if( !R[in] ) R[in] = ++last;
        return ask(a, b, mid + 1, r, R[in]);
    }
    if( mid >= b ) {
        if( !L[in] ) L[in] = ++last;
        return ask(a, b, l, mid, L[in]);
    }
    check(in);
    return ask(a, b, l, mid, L[in]) + ask(a, b, mid + 1, r, R[in]);
}

void solve(){
    int q, c = 0;
    cin >> q;
    while(q--) {
        int tp, x, y;
        cin >> tp >> x >> y;
        x += c;
        y += c;
        if( tp == 1 ) {
            int res = ask(x, y, 1, 1e9, 1);
            c = res;
            cout << res << '\n';
        } else {
            update(x, y, 1, 1e9, 1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen("stdin", "r",stdin);  
    // freopen("stdout", "w",stdout);
    
    int t=1;
    // cin>>t;
    while(t--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...