Submission #1102881

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102881	2024-10-19T07:14:53 Z	ardadut	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	205 ms	188612 KB

apple

#include <bits/stdc++.h>
    
#define ll long long
#define pb push_back
#define endl "\n"
#define vec vector<ll>
#define vecvec vector<vector<ll>>
    
using namespace std;
    
/*#define FileName ""
string Ghhhh = ".in";
string Ghhhhh = ".out";
ifstream Girdi(FileName + Ghhhh);
ofstream Cikti(FileName + Ghhhhh);
#define cin Girdi
#define cout Cikti*/

struct Node{
    int tl,tr,lc = -1,rc = -1,lazy = 0;
    int sum = 0;
};

const int maxn = 123456;
Node tree[64*maxn];
int cnt = 2;

inline void child_maker(int node){
    if(tree[node].lc == -1){
        int mid = (tree[node].tl + tree[node].tr) / 2;
        tree[node].lc = cnt++;
        tree[tree[node].lc].tl = tree[node].tl;
        tree[tree[node].lc].tr = mid;

        tree[node].rc = cnt++;
        tree[tree[node].rc].tl = mid+1;
        tree[tree[node].rc].tr = tree[node].tr;
    }
}

inline void push(int node){
    if(tree[node].lazy){
        tree[node].sum = tree[node].tr - tree[node].tl + 1;

        child_maker(node);

        tree[tree[node].rc].lazy = tree[tree[node].lc].lazy = 1;
        tree[node].lazy = 0;
    }
}

inline void update(int ul, int ur, int node = 1){

    push(node);
    
    if(ul > ur) return;
    if(ul <= tree[node].tl and tree[node].tr <= ur){
        tree[node].lazy = 1;
        push(node);
        return;
    }

    child_maker(node);

    int mid = (tree[node].tl + tree[node].tr) / 2;
    if(ur <= mid) update(ul,ur,tree[node].lc);
    else if(ul > mid) update(ul,ur,tree[node].rc);
    else{
        update(ul,mid,tree[node].lc);
        update(mid+1,ur,tree[node].rc);
    }

    push(tree[node].lc);
    push(tree[node].rc);

    tree[node].sum = tree[tree[node].lc].sum + tree[tree[node].rc].sum;
}

inline int query(int ql, int qr, int node = 1){

    push(node);

    if(ql <= tree[node].tl and tree[node].tr <= qr) return tree[node].sum;

    child_maker(node);

    int mid = (tree[node].tl + tree[node].tr) / 2;

    if(qr <= mid) return query(ql,qr,tree[node].lc);
    else if(ql > mid) return query(ql,qr,tree[node].rc);
    else return query(ql,mid,tree[node].lc) + query(mid+1,qr,tree[node].rc);

}

inline void solve(){

    int m;
    cin >> m;

    tree[1].sum = 0;
    tree[1].lazy = 0;
    tree[1].tl = 1;
    tree[1].tr = 1e9;

    int c = 0;

    while(m--){
        int d,x,y;
        cin >> d >> x >> y;

        if(d == 1){
            c = query(x + c,y + c);
            cout << c << endl;
        }else update(x + c, y + c);
    }
    
}
    
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    //cin >> t;
    while(t--){
        solve();
    }
    
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	36 ms	185936 KB	Output is correct
2	Correct	42 ms	185932 KB	Output is correct
3	Correct	42 ms	185932 KB	Output is correct
4	Correct	46 ms	186044 KB	Output is correct
5	Correct	51 ms	186188 KB	Output is correct
6	Correct	57 ms	186196 KB	Output is correct
7	Correct	55 ms	185972 KB	Output is correct
8	Correct	103 ms	186932 KB	Output is correct
9	Correct	174 ms	188132 KB	Output is correct
10	Correct	198 ms	187980 KB	Output is correct
11	Correct	175 ms	187980 KB	Output is correct
12	Correct	172 ms	187984 KB	Output is correct
13	Correct	159 ms	188408 KB	Output is correct
14	Correct	143 ms	188360 KB	Output is correct
15	Correct	190 ms	188476 KB	Output is correct
16	Correct	205 ms	188492 KB	Output is correct
17	Correct	158 ms	188492 KB	Output is correct
18	Correct	161 ms	188468 KB	Output is correct
19	Correct	192 ms	188492 KB	Output is correct
20	Correct	198 ms	188612 KB	Output is correct