Submission #194973

#	Time	Username	Problem	Language	Result	Execution time	Memory
194973		sealnot123	Jousting tournament (IOI12_tournament)	C++14	0 / 100	1079 ms	3932 KiB

tournament

//#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[u]) 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
*/

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:86:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k,a,b,d;
          ^
tournament.cpp:86:12: warning: unused variable 'a' [-Wunused-variable]
  int i,j,k,a,b,d;
            ^
tournament.cpp:86:14: warning: unused variable 'b' [-Wunused-variable]
  int i,j,k,a,b,d;
              ^
tournament.cpp:86:16: warning: unused variable 'd' [-Wunused-variable]
  int i,j,k,a,b,d;
                ^

• Subtask 1: 0 / 17
• Subtask 2: 0 / 32
• Subtask 3: 0 / 51