Submission #919237

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919237	2024-01-31T13:22:06 Z	ibrahim001	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	441 ms	121128 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	2392 KB	Output is correct
2	Correct	1 ms	2392 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	18 ms	2904 KB	Output is correct
5	Correct	22 ms	6744 KB	Output is correct
6	Correct	22 ms	6736 KB	Output is correct
7	Correct	22 ms	6736 KB	Output is correct
8	Correct	152 ms	26996 KB	Output is correct
9	Correct	315 ms	44008 KB	Output is correct
10	Correct	317 ms	50328 KB	Output is correct
11	Correct	348 ms	52784 KB	Output is correct
12	Correct	351 ms	55044 KB	Output is correct
13	Correct	304 ms	65616 KB	Output is correct
14	Correct	320 ms	67400 KB	Output is correct
15	Correct	441 ms	118064 KB	Output is correct
16	Correct	421 ms	119628 KB	Output is correct
17	Correct	307 ms	70496 KB	Output is correct
18	Correct	318 ms	70596 KB	Output is correct
19	Correct	423 ms	119900 KB	Output is correct
20	Correct	428 ms	121128 KB	Output is correct