Submission #919344

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
919344	2024-01-31T15:42:58 Z	ibrahim001	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	468 ms	193092 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*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);
        }
    }
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	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	-