Submission #970528

#	Time	Username	Problem	Language	Result	Execution time	Memory
970528		islam998	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	358 ms	235936 KiB

apple

#include <bits/stdc++.h>
#define ll long long
#define endl '\n'
#define nots0fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define vl vector<ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define pb push_back
#define in insert
#define all(v) v.begin(), v.end()
#define mid(a, b) ((a) + (b)) / 2
using namespace std;
mt19937 rng(time(NULL)); // rng()%(r - l + 1) + l

const int MX = 1e5 + 5 , inf = 1e9 + 99, sz = 5005, mod = 1000000007, N = 1e6 + 31, MOD = 998244353;
const ll INF = 100000000000000007;

ll sg[MX * 80], lz[MX * 80], L[MX * 80], R[MX * 80], last = 1;

void check(ll node){
    if(!L[node]){
        L[node] = ++last;
    }
    if(!R[node]){
        R[node] = ++last;
    }
}

void relax(ll k, ll l, ll r){
    if(!lz[k]) return ;
    sg[k] = (r - l + 1);
    if(l == r){
        lz[k] = 0;
        return ;
    }
    check(k);
    lz[L[k]] += lz[k];
    lz[R[k]] += lz[k];
    lz[k] = 0;
}

void update(ll k, ll a, ll b, ll l, ll r){
    relax(k, a, b);
    if(l > b || r < a){
        return ;
    }
    if(l <= a && r >= b){
        lz[k]++;
        relax(k, a, b);
        return ;
    }
    int mid = mid(a, b);
    if (l > mid){
        if (!R[k]) R[k] = ++last;
        update(R[k], mid + 1, b, l, r);
    }
    else if (r <= mid){
        if (!L[k]) L[k] = ++last;
        update(L[k], a, mid, l, r);
    }
    else{
        check(k);
        update(L[k], a, mid, l, r);
        update(R[k], mid + 1, b, l, r);
    }
    relax(L[k], a, mid);
    relax(R[k], mid + 1, b);
    sg[k] = sg[L[k]] + sg[R[k]];
}

ll get(ll k, ll a, ll b, ll l, ll r){
    relax(k, a, b);
    if(l > b || r < a){
        return 0;
    }
    if(l <= a && r >= b){
        return sg[k];
    }
    int mid = mid(a, b);
    if (l > mid){
        if (!R[k]) R[k] = ++last;
        return get(R[k], mid + 1, b, l, r);
    }
    else if (r <= mid){
        if (!L[k]) L[k] = ++last;
        return get(L[k], a, mid, l, r);
    }
    check(k);
    return get(L[k], a, mid, l, r) + get(R[k], mid + 1, b, l, r);
}

void solve () {
    ll q, n = 1e9, plus = 0, res = 0;
    cin >> q;    
    while(q--){
        ll type, l, r;
        cin >> type >> l >> r;
        l += plus;
        r += plus;
        if(type == 1){
            res = get(1, 1, n, l, r);
            plus = res;
            cout << res << endl;
        }
        else{
            update(1, 1, n, l, r);
        }
    }
}

signed main(){
    nots0fast
    int test = 1;
    for(int tst = 1; tst <= test; tst++) {
        solve();
        cout << endl;
    }
    return 0;
}

• Subtask 1: 100 / 100