Submission #105176

#	Time	Username	Problem	Language	Result	Execution time	Memory
105176		eriksuenderhauf	Jousting tournament (IOI12_tournament)	C++11	100 / 100	189 ms	9004 KiB

tournament

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long int ll;
const int MAXN = 2e5 + 5;
int n, BIT[MAXN], sm[MAXN], cnt[MAXN];
set<int> act;

int sum(int ind) {
	ind++;
	int ret = 0;
	while (ind > 0) {
		ret += BIT[ind];
		ind -= ind & -ind;
	}
	return ret;
}

void upd(int ind, int val) {
	ind++;
	while (ind <= n) {
		BIT[ind] += val;
		ind += ind & -ind;
	}
}

int qry(int val) {
	int lo = 0, hi = n - 1, ret = -1;
	while (lo <= hi) {
		int mi = (lo + hi) / 2;
		if (sum(mi) <= val)
			ret = mi, lo = mi + 1;
		else
			hi = mi - 1;
	}
	return ret;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	n = N;
	for (int i = 0; i < n; i++) {
		sm[i] = sm[i - 1];
		if (i < n - 1 && K[i] > R)
			sm[i]++;
	}
	for (int i = 0; i < n; i++) {
		upd(i, 1);
		act.insert(i);
	}
	for (int i = 0; i < C; i++) {
		int l = qry(S[i]) + 1, r = qry(E[i] + 1);
		vi tmp;
		for (auto it = act.find(l); it != act.end() && *it <= r; it++)
			tmp.pb(*it);
		for (int j = 0; j < tmp.size(); j++) {
			upd(tmp[j], -1);
			act.erase(tmp[j]);
		}
		upd(l, 1);
		act.insert(l);
		if (sm[l - 1] == sm[r - 1])
			cnt[l]++, cnt[r + 1]--;
	}
	pii ret = {0, 0};
	for (int i = 0; i < n; i++) {
		cnt[i] += cnt[i - 1];
		ret = max(ret, {cnt[i], -i});
	}
	return -ret.se;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:64:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < tmp.size(); j++) {
                   ~~^~~~~~~~~~~~

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