Submission #58088

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
58088	2018-07-16T19:05:51 Z	Benq	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	95 ms	30452 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	492 KB	Output is correct
3	Correct	2 ms	716 KB	Output is correct
4	Correct	6 ms	908 KB	Output is correct
5	Correct	9 ms	1188 KB	Output is correct
6	Correct	10 ms	1372 KB	Output is correct
7	Correct	7 ms	1540 KB	Output is correct
8	Correct	25 ms	3516 KB	Output is correct
9	Correct	48 ms	6864 KB	Output is correct
10	Correct	45 ms	8772 KB	Output is correct
11	Correct	55 ms	10696 KB	Output is correct
12	Correct	95 ms	12588 KB	Output is correct
13	Correct	62 ms	14880 KB	Output is correct
14	Correct	50 ms	17048 KB	Output is correct
15	Correct	61 ms	19352 KB	Output is correct
16	Correct	58 ms	21488 KB	Output is correct
17	Correct	57 ms	23772 KB	Output is correct
18	Correct	55 ms	26008 KB	Output is correct
19	Correct	61 ms	28284 KB	Output is correct
20	Correct	60 ms	30452 KB	Output is correct