Submission #1284882

#	Time	Username	Problem	Language	Result	Execution time	Memory
1284882		dobri_oke	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	411 ms	260380 KiB

apple

#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define int long long

const int N = 1e6+100;

int q, t[N * 30], L[N * 30], R[N * 30], z[N * 30], cntv = 2;

void push(int v, int l, int r){
    if(z[v] != 0){
        t[v] = r - l + 1;
        if(l != r){
            if(L[v] == 0) L[v] = cntv++;
            if(R[v] == 0) R[v] = cntv++;
            z[L[v]] = 1;
            z[R[v]] = 1;
        }
        z[v] = 0;
    }
}
void upd(int v, int l, int r, int ll, int rr){
    push(v, l, r);
    if(ll <= l && r <= rr){
        z[v]++;
        push(v, l, r);
        return;
    }
    if(l > rr || ll > r) return;
    int m = (l + r) / 2;
    if(L[v] == 0) L[v] = cntv++;
    if(R[v] == 0) R[v] = cntv++;
    upd(L[v], l, m, ll, rr);
    upd(R[v], m + 1, r, ll, rr);
    t[v] = t[L[v]] + t[R[v]];
}
int get(int v, int l, int r, int ll, int rr){
    push(v, l, r);
    if(ll <= l && r <= rr) return t[v];
    if(l > rr || ll > r) return 0;
    int m = (l + r) / 2;
    if(L[v] == 0) L[v] = cntv++;
    if(R[v] == 0) R[v] = cntv++;
    return get(L[v], l, m, ll, rr) + get(R[v], m + 1, r, ll, rr);
}
void solve(){
    cin >> q;
    int c = 0;
    t[1] = 1;
    while(q--){
        int d, x, y;
        cin >> d >> x >> y;
        if(d == 2){
            upd(1, 1, 1e9, x + c, y + c);
        }
        else{
            c = get(1, 1, 1e9, x + c, y + c);
            cout << c << '\n';
        }
    }
}

signed main(){   
    ios_base::sync_with_stdio(0);   cin.tie(0);
    //freopen("promote.in","r",stdin);
    //freopen("promote.out","w",stdout);
    int tt=1;
   // cin >> tt;
    while(tt--){
        solve();
    }
}

• Subtask 1: 100 / 100