Submission #208822

#	Time	Username	Problem	Language	Result	Execution time	Memory
208822		bensonlzl	Jousting tournament (IOI12_tournament)	C++14	100 / 100	71 ms	5744 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;
typedef pair<int,pi> pii;

int par[100005], sz[100005], l[100005], r[100005], badpos[100005], ans[100005];
int ft[100005];
vector<pii> v;

int find_par(int x){
	if (par[x] != x) par[x] = find_par(par[x]);
	return par[x];
}

void merg(int x, int y){
	int X = find_par(x), Y = find_par(y);
	if (X == Y) return;
	if (sz[X] < sz[Y]) swap(X,Y);
	par[Y] = X;
 	sz[X] += sz[Y];
 	l[X] = min(l[X],l[Y]);
 	r[X] = max(r[X],r[Y]);
}

int get_endpoint(int x){
	return r[find_par(x)];
}

void update(int x){
	for (; x <= 100001; x += (x & -x)) ft[x]--;
}

int GetBestPosition(int N, int C, int R, int *K,  int *S, int *E){
	for (int i = 1; i <= N+1; ++i){
		par[i] = i;
		sz[i] = 1;
		l[i] = r[i] = i;
		ft[i] = 1;
	}
	for (int i = 0; i < N-1; ++i) badpos[i+1] = (K[i] > R ? 1 : 0) + badpos[i];
	for (int i = 1; i < 18; ++i){
		for (int j = (1 << i); j <= N; j += (1 << i)){
			ft[j] += ft[j - (1 << (i-1))];
		}
	}
	for (int i = 0; i < C; ++i){
		int l = S[i]+1, r = E[i]+1;
		int idx = 0, sum = 0;
		for (int i = 18; i >= 0; --i){
			if (idx + (1 << i) > N) continue;
			if (sum + ft[idx + (1 << i)] < l){
				sum += ft[idx + (1 << i)];
				idx += (1 << i);
			}
		}
		idx++;
		vector<int> components;
		while (components.size() < r-l+1){
			components.push_back(idx);
			idx = get_endpoint(idx)+1;
		}
		int lpt = components[0], rpt = get_endpoint(components.back());

		if (badpos[rpt-1] == badpos[lpt-1]){
			ans[lpt]++;
			ans[rpt+1]--;
		}

		v.push_back(pii(i,pi(components[0],get_endpoint(components.back()))));
		for (int i = 1; i < components.size(); ++i){
			merg(components[i-1],components[i]);
			update(components[i]);
		}
		
		//cout << v.back().second.first << ' ' << v.back().second.second << '\n';
	}
	int maxi = 0, maxdex = 0, cur = 0;
	for (int i = 1; i <= N; ++i){
		cur += ans[i];
		if (cur > maxi){
			maxdex = i-1;
			maxi = cur;
		}
	}

	return maxdex;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:60:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (components.size() < r-l+1){
          ~~~~~~~~~~~~~~~~~~^~~~~~~
tournament.cpp:72:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < components.size(); ++i){
                   ~~^~~~~~~~~~~~~~~~~~~

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