Submission #58088

#	Time	Username	Problem	Language	Result	Execution time	Memory
58088		Benq	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	95 ms	30452 KiB

apple

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;

int mag(pi d) { return max(d.s-d.f+1,0); }

int inter(pi a, pi b) { return mag({max(a.f,b.f),min(a.s,b.s)}); }

struct {
    struct tnode {
        pi d, D; 
        int pri, sz;
        tnode *c[2];
    
        tnode (pi _d) {
            d = D = _d;
            pri = rand()+(rand()<<15);
            sz = mag(d);
            c[0] = c[1] = NULL;
        }
        
        void inOrder(bool f = 0) {
            if (c[0]) c[0]->inOrder();
            cout << d.f << " " << d.s << " | ";
            if (c[1]) c[1]->inOrder();
            if (f) cout << "\n------------\n";
        }
    };
    
    int getsz(tnode* x) { return x?x->sz:0; }
    
    void recalc(tnode* x) {
        x->sz = getsz(x->c[0])+mag(x->d)+getsz(x->c[1]);
        x->D = x->d; 
        if (x->c[0]) x->D.f = x->c[0]->D.f;
        if (x->c[1]) x->D.s = x->c[1]->D.s;
    }
    
    pair<tnode*,tnode*> split(tnode* t, int v) { // >= v goes to the right
        if (!t) return {t,t};
        
        if (v <= t->d.s) {
            auto p = split(t->c[0], v); 
            t->c[0] = p.s; recalc(t);
            return {p.f, t};
        } else {
            auto p = split(t->c[1], v); 
            t->c[1] = p.f; recalc(t);
            return {t, p.s};
        }
    }
    
    tnode* merge(tnode* l, tnode* r) {
        if (!l) return r; 
        if (!r) return l;
        
        if (l->pri > r->pri) {
            l->c[1] = merge(l->c[1],r);
            recalc(l);
            return l;
        } else {
            r->c[0] = merge(l,r->c[0]);
            recalc(r);
            return r;
        }
    }
    
    pi getFst(tnode* x) {
        if (!x) return {MOD,MOD};
        return min(x->d,getFst(x->c[0]));
    }
    
    tnode* remFst(tnode* x) {
        if (x->c[0]) {
            x->c[0] = remFst(x->c[0]);
            recalc(x);
            return x;
        } 
        return x->c[1];
    }
    
    // PUBLIC 
    tnode* root;

    pi extract(int X, int Y) {
        auto a = split(root,X);
        pi b = getFst(a.s);
        
        pi ans = {MOD,MOD};
        if (b.f <= Y) {
            ans = b;
            a.s = remFst(a.s);
        }
        
        root = merge(a.f,a.s);
        return ans;
    }
    
    void insert(int X, int Y) {
        auto a = split(root,X);
        root = merge(merge(a.f,new tnode({X,Y})),a.s);
    }
    
    int query(tnode* cur, pi x) {
        if (!cur) return 0;
        if (cur->D.s < x.f || x.s < cur->D.f) return 0;
        if (x.f <= cur->D.f && cur->D.s <= x.s) return cur->sz;
        return query(cur->c[0],x)+inter(cur->d,x)+query(cur->c[1],x);
    }
    
    int query(int X, int Y) { return query(root,{X,Y}); }
} treap;

int M,C;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> M;
    F0R(i,M) {
        int D,X,Y; cin >> D >> X >> Y; X += C, Y += C;
        if (D == 1) {
            C = treap.query(X,Y);
            cout << C << "\n";
        } else {
            while (1) {
                auto a = treap.extract(X,Y);
                if (a.f == MOD) break;
                X = min(X,a.f), Y = max(Y,a.s);
            }
            treap.insert(X,Y);
        }
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
*/

• Subtask 1: 100 / 100