Submission #1275263

#TimeUsernameProblemLanguageResultExecution timeMemory
1275263al95ireyizMonkey and Apple-trees (IZhO12_apple)C++20
100 / 100
361 ms253616 KiB
#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 2e5 + 5;

ll n, m, k = 0;

#define DEF NULL
struct IMPL{
    IMPL *lt = DEF, *rt = DEF;
    int cm = 0, l, r, lazy = 0;
    IMPL(ll l, ll r) : l(l), r(r) {}
    void drop(){
        if(lazy == 0) return;
        if(l != r){
            ll md = (l + r) >> 1;
            if(lt == DEF) lt = new IMPL(l, md);
            if(rt == DEF) rt = new IMPL(md + 1, r);
            lt->lazy = 1;
            lt->cm = md - l + 1;
            rt->lazy = 1;
            rt->cm = r - (md + 1) + 1;
        }
        lazy = 0;
    }
    void upd(ll _l, ll _r){
        bool in = _l <= l and r <= _r;
        bool ot = _l <= r and l <= _r;
        if(in){
            lazy = 1;
            cm = (r - l + 1);
            return;
        }
        drop();
        if(ot){
            ll md = (l + r) >> 1;
            if(_l <= md){
                if(lt == DEF) lt = new IMPL(l, md);
                lt->upd(_l, _r);
            }
            if(_r > md){
                if(rt == DEF) rt = new IMPL(md + 1, r);
                rt->upd(_l, _r);
            }
            cm = (lt == DEF ? 0 : lt->cm) + (rt == DEF ? 0 : rt->cm);
        }
    }
    ll get(ll _l, ll _r){
        bool in = _l <= l and r <= _r;
        bool ot = _l <= r and l <= _r;
        if(in) return cm;
        drop();
        if(ot){
            return (lt != DEF ? lt->get(_l, _r) : 0) +
                   (rt != DEF ? rt->get(_l, _r) : 0);
        }
        return 0;
    }
};
void _() {
    ll c = 0;
    cin >> n;
    IMPL tree(1, INF);
    for(ll i = 1, t, x, y; i <= n; i ++){
        cin >> t >> x >> y;
        if(t == 1){
            ll z = tree.get(x + c, y + c);
            c = z;
            cout << z << '\n';
        }
        else{
            tree.upd(x + c, y + c);
        }
    }
}
signed main() {
    ll tm = clock();
    cin.tie(0)->sync_with_stdio(0);
    ll t = 1;
    // cin >> t;
    for(ll tt = 1; tt <= t; tt ++) _();
    cerr << "\n\033[1;31mTime: \033[1;30m" \
         << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...