Submission #1281677

#TimeUsernameProblemLanguageResultExecution timeMemory
1281677zadniprovskaMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
237 ms69012 KiB
#include <bits/stdc++.h>

using namespace std;

#define ll int
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front

const ll DIM = 1e5 * 50 + 7;
const ll INF = 1e18;
const ll mod = 1e9 + 7;
const ll maxlog = 20;
const ll bsize = 350;

ll T[DIM], pr[DIM], leftt[DIM], rightt[DIM];
ll allnodes = 0;

ll left (ll v) {
    if (leftt[v] == 0) leftt[v] = ++allnodes; 
    return leftt[v];
}

ll right (ll v) {
    if (rightt[v] == 0) rightt[v] = ++allnodes;
    return rightt[v];
}

void push (ll v, ll tl, ll tr) {

    if (tl == tr || pr[v] == 0) return;

    pr[left(v)] = 1;
    pr[right(v)] = 1;

    ll tm = (tl + tr) >> 1;
    T[left(v)] = tm - tl + 1;
    T[right(v)] = tr - tm;

    pr[v] = 0;

}

void update (ll v, ll tl, ll tr, ll L, ll R) {

    if (R < tl || tr < L) {
        return;
    }

    if (L <= tl && tr <= R) {
        T[v] = tr - tl + 1;
        pr[v] = 1;

        return;
    }

    push(v, tl, tr);
    ll tm = (tl + tr) >> 1;
    update(left(v), tl, tm, L, R);
    update(right(v), tm+1, tr, L, R);
    
    T[v] = T[left(v)] + T[right(v)];

}

ll query (ll v, ll tl, ll tr, ll L, ll R) {

    if (R < tl || tr < L) return 0;

    if (L <= tl && tr <= R) return T[v];

    push(v, tl, tr);
    ll tm = (tl + tr) >> 1;

    return query(left(v), tl, tm, L, R) + query(right(v), tm+1, tr, L, R);

}

void solve () {

    ll m;
    cin >> m;

    ll c = 0;
    for (int i=1; i<=m; i++) {

        ll type, x, y;
        cin >> type >> x >> y;

        x += c; y += c;

        if (type == 1) {
            ll ans = query(0, 1, 1000000000, x, y);
            cout << ans << endl;
            c = ans;
        }
        else {
            update(0, 1, 1000000000, x, y);
        }

    }

}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);
    
    int ntest = 1;
    //cin >> ntest;
    while (ntest--){
        solve();
    }
    return 0;

}
;

Compilation message (stderr)

apple.cpp:16:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   16 | const ll INF = 1e18;
      |                ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...