Submission #58078

#	Time	Username	Problem	Language	Result	Execution time	Memory
58078		Benq	Weighting stones (IZhO11_stones)	C++14	100 / 100	401 ms	16860 KiB

stones

#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;

struct tnode {
    int val, les, pri;
    int sz, mn, lazy;
    tnode *c[2];

    tnode (int _val, int _les) {
        val = _val, les = _les, pri = rand()+(rand()<<15);
        sz = 1, mn = les, lazy = 0;
        c[0] = c[1] = NULL;
    }
    
    void inOrder(bool f = 0) {
        if (c[0]) c[0]->inOrder();
        cout << val << " ";
        if (c[1]) c[1]->inOrder();
        if (f) cout << "\n------------\n";
    }
};

    
int getsz(tnode* x) { return x?x->sz:0; }

int getmn(tnode* x) { return x?x->mn:MOD; }

void prop(tnode* x) {
    if (!x) return;
    x->les += x->lazy, x->mn += x->lazy;
    F0R(i,2) if (x->c[i]) x->c[i]->lazy += x->lazy;
    x->lazy = 0;
}

void recalc(tnode* x) {
    prop(x);
    F0R(i,2) if (x->c[i]) prop(x->c[i]);
    // sz
    x->sz = 1; F0R(i,2) x->sz += getsz(x->c[i]);
    
    // mn
    x->mn = getmn(x->c[0]);
    x->mn = min(x->mn,x->les-getsz(x->c[0]));
    x->mn = min(x->mn,getmn(x->c[1])-1-getsz(x->c[0]));
}

pair<tnode*,tnode*> split(tnode* t, int v) { // >= v goes to the right
    prop(t);
    if (!t) return {t,t};
    
    if (v <= t->val) {
        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) {
    prop(l), prop(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;
    }
}

tnode* upd(tnode* x, int y, int z) { // # less - pos 
    auto a = split(x,y);
    return merge(merge(a.f,new tnode(y,z)),a.s);
}

tnode* t[2];
int N;

void upd(int x, int y) {
    auto a = split(t[y^1],x);
    if (a.s) a.s->lazy ++;
    t[y] = upd(t[y],x,getsz(a.f)); // insert 
    t[y^1] = merge(a.f,a.s);
}

// >= sz(b)-(sz(a)-1)
bool majorize(tnode* a, tnode* b) {
    if (getsz(a) < getsz(b)) return 0;
    prop(a);
    return a->mn >= getsz(b)-(getsz(a)-1);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N;
    F0R(i,N) {
        int x,y; cin >> x >> y; 
        upd(x,y-1);
        /*if (t[0]) {
            cout << "A\n";
            prop(t[0]);
            t[0]->inOrder();
            cout << "\n";
            cout << "OH " << t[0]->val << " " << t[0]->les << " " << t[0]->mn << "\n";
        }
        if (t[1]) {
            cout << "B\n";
            t[1]->inOrder();
            cout << "\n";
        }*/
        if (majorize(t[0],t[1])) cout << '>';
        else if (majorize(t[1],t[0])) cout << '<';
        else cout << '?';
        cout << "\n";
        // cout << "\n";
    }
}

/* 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