Submission #1266509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266509		herreinstein	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	495 ms	327680 KiB

apple

#include <bits/stdc++.h>
#define int long long int
#define ff first
#define ss second
const int MOD = 998244353;
const int N = 2e5 + 5;
using namespace std;
struct node{
    int l, r, val, lazy;
    int L = -1, R = -1;
};
vector<node> dy;
int newnode(){
    dy.push_back({0,0,0,0,-1,-1});
    return dy.size()-1;
}
void ekle(int i){
    if(dy[i].l != dy[i].r && dy[i].L == -1){
        dy[i].L = newnode();
        dy[i].R = newnode();
        int m = (dy[i].l + dy[i].r) >> 1;
        dy[dy[i].L].l = dy[i].l;
        dy[dy[i].L].r = m;
        dy[dy[i].R].l = m+1;
        dy[dy[i].R].r = dy[i].r;
    }
}
void push(int i){
    ekle(i);
    if(dy[i].lazy == 1){
        dy[i].val = dy[i].r - dy[i].l + 1;
    }
    if(dy[i].l != dy[i].r && dy[i].lazy == 1){
        dy[dy[i].L].lazy = dy[i].lazy;
        dy[dy[i].R].lazy = dy[i].lazy;
    }
    // cout << i << " " << dy[i].l << " " << dy[i].r << " " << dy[i].val << endl;
}
void up(int i, int ql, int qr){
    push(i);
    // cout << i  << " " << dy[i].l << " " << dy[i].r << " " << ql << " " << qr << endl;
    if(dy[i].l >= ql && qr >= dy[i].r){
        dy[i].lazy = 1;
        push(i);
            // cout << i << " " << dy[i].l << " " << dy[i].r << " " << dy[i].val << endl;

        return;
    }
    if(ql > dy[i].r || qr < dy[i].l){
        return;
    }
    up(dy[i].L, ql, qr);
    up(dy[i].R, ql, qr);
    dy[i].val = dy[dy[i].L].val + dy[dy[i].R].val;
            // cout << i << " " << dy[i].l << " " << dy[i].r << " " << dy[i].val << endl;

}
int find(int i, int ql, int qr){
    push(i);
    // cout << i << " " << dy[i].l << " " << dy[i].r << " " << ql << " " << qr << " " << dy[i].val << endl;
    if(ql <= dy[i].l && qr >= dy[i].r){
        return dy[i].val;
    }
    if(ql > dy[i].r || qr < dy[i].l){
        return 0;
    }
    return find(dy[i].L, ql, qr) + find(dy[i].R, ql, qr);
}
void solve(){
    int n;
    cin >> n;
    newnode();
    newnode();
    dy[1].l = 1, dy[1].r = 1000000000;
    int e = 0;
    for(int i = 0; i < n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        if(x == 2){
            up(1, y+e, z+e);
        }
        else{
            e = find(1, y+e, z+e);
            cout << e << endl;
        }
    }
}
int32_t main(){
    
    int t;
    // cin >> t;
    t = 1;
    while(t--) solve();
}

• Subtask 1: 0 / 100