Submission #1102717

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1102717	2024-10-18T18:04:10 Z	ardadut	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	36 ms	262144 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;
    int sum = 0;
};

const int maxn = 1e6;
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 <= 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(qr <= 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

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	36 ms	262144 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-