oj.uz

Submission #208822

# Submission time Handle Problem Language Result Execution time Memory
208822 2020-03-12T08:41:01 Z bensonlzl Jousting tournament (IOI12_tournament) C++14
100 / 100
 71 ms 5744 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 536 KB Output is correct
2 Correct 8 ms 680 KB Output is correct
3 Correct 6 ms 632 KB Output is correct
4 Correct 7 ms 760 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 7 ms 636 KB Output is correct
7 Correct 8 ms 632 KB Output is correct
8 Correct 8 ms 632 KB Output is correct
9 Correct 6 ms 504 KB Output is correct
10 Correct 8 ms 760 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2744 KB Output is correct
2 Correct 70 ms 5616 KB Output is correct
3 Correct 30 ms 3956 KB Output is correct
4 Correct 69 ms 5616 KB Output is correct
5 Correct 68 ms 5616 KB Output is correct
6 Correct 60 ms 4852 KB Output is correct
7 Correct 71 ms 5744 KB Output is correct
8 Correct 68 ms 5616 KB Output is correct
9 Correct 27 ms 3748 KB Output is correct
10 Correct 31 ms 3580 KB Output is correct