| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 17144 | murat | Jousting tournament (IOI12_tournament) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#define ROF(ii,aa,bb) for(int ii=aa;ii>=bb;ii--)
#define type(x) __typeof(x.begin())
#define orta (bas + son >> 1)
#define sag (k + k + 1)
#define sol (k + k)
#define pb push_back
#define mp make_pair
#define nd second
#define st first
#define endl '\n'
typedef pair < int ,int > pii;
typedef long long ll;
const long long linf = 1e18+5;
const int mod = (int) 1e9 + 7;
const int logN = 17;
const int inf = 1e9;
const int N = 2e5 + 5;
class node {
public:
int xx, yy, sum;
node() { xx = yy = sum = 0; }
} ST[N << 2];
int R, mx[N << 2], a[N], n, m, x, y, z, t, cc, ans, l[N], r[N];
vector< pii > s[N], f[N];
pii ST3[N << 2];
node init(int k, int bas, int son) {
if(bas == son) { ST[k].xx = ST[k].yy = bas; ST[k].sum = 1; return ST[k]; }
init(sol, bas, orta);
init(sag, orta+1, son);
ST[k].xx = bas;
ST[k].yy = son;
ST[k].sum = son - bas + 1;
}
pii query(int k, int bas, int son, int x) {
if(bas == son) return mp(ST[k].xx, ST[k].yy);
if(ST[sol].sum >= x) return query(sol, bas, orta, x);
return query(sag, orta+1, son, x-ST[sol].sum);
}
node update(int k, int bas, int son, int x) {
if(bas == son) { ST[k].xx = ST[k].yy = ST[k].sum = 0; return ST[k]; }
if(ST[sol].sum >= x) update(sol, bas, orta, x);
else update(sag, orta+1, son, x - ST[sol].sum);
ST[k].sum = ST[sol].sum + ST[sag].sum;
return ST[k];
}
node make(int k, int bas, int son, int x, pii t) {
if(x < 0) return ST[k];
if(bas == son) { ST[k].xx = t.st; ST[k].yy = t.nd; ST[k].sum = 1; return ST[k]; }
if(ST[sol].sum >= x) make(sol, bas, orta, x, t);
else make(sag, orta+1, son, x - ST[k].sum, t);
ST[k].sum = ST[sol].sum + ST[sag].sum;
return ST[k];
}
int init2(int k, int bas, int son) {
if(bas == son) return mx[k] = a[bas];
return mx[k] = max(init2(sag, orta+1, son), init2(sol, bas, orta));
}
int query2(int k, int bas, int son, int x, int y) {
if(bas > y || son < x) return 0;
if(x <= bas && son <= y) return mx[k];
return max(query2(sol, bas, orta, x, y), query2(sag, orta+1, son, x, y));
}
pii update3(int k, int bas, int son, int x, int t) {
if(bas > x || son < x) return ST3[k];
if(bas == son) return ST3[k] = mp(t, t != 0);
update3(sol, bas, orta, x, t);
update3(sag, orta + 1, son, x, t);
return ST3[k] = mp(max(ST3[sol].st, ST3[sag].st), ST3[sol].nd + ST3[sag].nd);
}
int take3(int k, int bas, int son) {
if(bas == son) return ST3[k].nd && ST3[k].st <= R;
if(ST3[sol].st <= R) return take3(sag, orta+1, son) + ST3[sol].nd;
return take3(sag, orta+1, son);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
for(int i = 1; i < n; i++) {
a[i] = ++K[i-1];
} ++R;
::R = R;
init(1, 1, n);
init2(1, 1, n);
for(int i = 1; i <= C; i++) {
int x = S[i-1] + 1,
y = E[i-1] + 1,
xx = query(1, 1, n, x).st,
yy = query(1, 1, n, y).nd;
for(int j = x; j < y; j++) {
update(1, 1, n, x);
}
make(1, 1, n, y, mp(xx, yy));
int mx = query2(1, 1, n, xx, yy-1);
s[xx].pb(mp(i, mx));
f[yy-1].pb(mp(i, mx));
}
int ans = 0, aaa = 0;
for(int i = 1; i <= n; i++) {
foreach(it, s[i]) {
update3(1, 1, C, it->st, it->nd);
}
int cc = take3(1, 1, C);
if(cc > ans) { ans = cc; aaa = i - 1; }
foreach(it, f[i]) {
update3(1, 1, C, it->st, 0);
}
}
return cc;
}