답안 #919344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
919344 2024-01-31T15:42:58 Z ibrahim001 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
468 ms 193092 KB
#include "bits/stdc++.h"
#define intt long long
using namespace std;
const intt inf = 1e18;
const int sz = 1e5+5;
int st[sz*60], lz[sz*60], L[sz*60], R[sz*60];
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);
        }
    }
}
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2492 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 19 ms 4696 KB Output is correct
5 Correct 22 ms 6488 KB Output is correct
6 Correct 24 ms 6352 KB Output is correct
7 Correct 22 ms 6492 KB Output is correct
8 Correct 161 ms 26984 KB Output is correct
9 Correct 371 ms 44228 KB Output is correct
10 Correct 361 ms 49504 KB Output is correct
11 Correct 331 ms 52888 KB Output is correct
12 Correct 368 ms 54096 KB Output is correct
13 Correct 322 ms 65736 KB Output is correct
14 Correct 340 ms 66460 KB Output is correct
15 Runtime error 468 ms 193092 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -