#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 recalc(tnode* x) {
// 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]));
}
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;
}
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
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
380 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
