| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 194951 | sealnot123 | Jousting tournament (IOI12_tournament) | C++14 | 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.
//#include "grader.cpp"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PLL;
typedef pair<int,int> PII;
typedef double D;
typedef long double LD;
const int N = 100003;
int p[N], fw[N], seg[N<<2], n, Rank, dp[N], L[N], R[N];
int* num;
set< pair<PII, int> > interval;
set< pair<PII, int> >::iterator it, it2;
vector<int> g[N];
int fin(int i){
if(p[i]==i) return i;
return p[i]=fin(p[i]);
}
void add(int a, int b){
while(a<N) fw[a] += b, a+=(a&-a);
}
int get(int a){
int b = 0;
while(a) b += fw[a], a-=(a&-a);
return b;
}
int bullshit(int a){ // binary search
int b = 0, c = 0;
for(int i=(1<<16); i>0; i>>=1){
int t = b + fw[c|i];
if(t <= a) b = t, c |= i;
//printf("zzzz%d %d\n",a,c);
}
return c;
}
int bs(int a){
int l=0, r=N-1;
while(l<r){
int m = (l+r)>>1;
if(get(m)<a) l = m+1;
else r = m;
}
return l;
}
void build(int l = 1, int r = n-1, int now = 1){
if(l == r){ seg[now] = num[l-1]; return ;}
int m = (l+r)>>1;
build(l, m, now<<1); build(m+1, r, now<<1|1);
seg[now] = max(seg[now<<1], seg[now<<1|1]);
}
int qu(int ll, int rr, int l = 1, int r = n-1, int now = 1){
if(l > rr || r < ll) return -1;
if(l >= ll && r <= rr) return seg[now];
int m = (l+r)>>1;
return max(qu(ll, rr, l, m, now<<1), qu(ll, rr, m+1, r, now<<1|1));
}
void dfs(int u){
if(dp[i]) return ;
int ch = (qu(L[u], R[u]-1)<Rank);
//printf("==%d (%d,%d) %d\n",u,L[u],R[u],ch);
dp[u] = -1;
for(int e : g[u]){
//printf("%d\n",e);
dfs(e);
dp[u] = max(dp[u], dp[e]);
}
if(g[u].empty()) dp[u] = (ch)?1:-1;
else if(dp[u]!=-1) dp[u] = (ch)?dp[u]+1:-1;
}
int GetBestPosition(int n1, int c, int r, int *K, int *S, int *E) {
// c is number of commands
// r is rank of the late knight
// K = rank of the knight in each positions (0 to n-1)
// S and E are just 'l' and 'r'
num = K;
n = n1;
Rank = r;
int i,j,k,a,b,d;
for(i=1;i<=n+1;i++) add(i, 1), p[i] = i;
for(i=0;i<c;i++){
int l = bullshit(S[i]+1);
L[i] = bs(S[i])+1;
int r = bullshit(E[i]+1);
R[i] = r;
it = interval.lower_bound({{L[i],0},0});
while(it != interval.end() && it->x.x >= L[i] && it->x.y <= R[i]){
it2 = it;
it++;
g[i].pb(it2->y);
interval.erase(it2);
}
//printf("##%d\n%d %d\n",i,L[i],R[i]);
interval.insert({{L[i], R[i]},i});
for(j = l; j < r; j=fin(j+1)){
//printf("xx%d\n",j);
add(j, -1);
p[j] = fin(j+1);
}
}
build();
dfs(c-1);
PII ans = (PII){-2, 0};
for(i=0;i<c;i++) ans = max((PII){dp[i], -i}, ans);
return -ans.y;
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1
*/