Submission #363017

#	Time	Username	Problem	Language	Result	Execution time	Memory
363017		8e7	Jousting tournament (IOI12_tournament)	C++14	100 / 100	128 ms	33132 KiB

tournament

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#define ll long long
#define maxn 200005
#define mod 1000000000
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;

vector<int> node[maxn];
int block[maxn];

pii getpos(int x) {
	int cnt = 0;
	while (true) {
		if (x < block[cnt]) {
			return make_pair(cnt, x);
		}
		x -= block[cnt];
		cnt++;
	}
}

int a[maxn], dep[maxn];
int tot;
vector<int> adj[maxn];
int best[maxn];
pii range[maxn];
void dfs(int n, int par) {
	if (n < tot) {
		range[n] = make_pair(n, n);
		best[n] = n;
	} else {
		range[n] = make_pair(1<<30, -1);
		best[n] = 1<<30;
	}
	for (int v:adj[n]) {
		if (v != par) {
			dfs(v, n);
			if (dep[v] + 1 > dep[n]) {
				dep[n] = dep[v] + 1;
				best[n] = best[v];
			} else if (dep[v] + 1 == dep[n]) {
				best[n] = min(best[n], best[v]);
			}
			range[n] = make_pair(min(range[n].ff, range[v].ff), max(range[n].ss, range[v].ss));
		}
	}

}

int sp[17][maxn];
inline int hbit(int x) {
	int ret = 0;
	while (x) {
		ret++, x>>=1;
	}
	return ret;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	tot = N;
	for (int i = 0;i < N - 1;i++) a[i] = K[i];
	int blocksiz = int(sqrt(N)), num = (N - 1 + blocksiz) / blocksiz;
	int ind = -1;
	for (int i = 0;i < N;i++) {
		if (i % blocksiz == 0) {
			block[ind] = node[ind].size();
			ind++;
		}
		node[ind].push_back(i);
	}
	block[ind] = node[ind].size();
	for (int i = 0;i < C;i++) {
		int add = N + i;
		pii s = getpos(S[i]), e = getpos(E[i]);
		//cout << s.ff << "  " << s.ss << endl;
		if (s.ff != e.ff) {
			for (int j = s.ss;j < node[s.ff].size();j++) {
				adj[add].push_back(node[s.ff][j]);
			}
			for (int j = 0;j < block[s.ff] - s.ss;j++) node[s.ff].pop_back();
			node[s.ff].push_back(add);
			block[s.ff] = node[s.ff].size();

			for (int j = s.ff + 1;j < e.ff;j++) {
				for (int k = 0;k < block[j];k++) {
					adj[add].push_back(node[j][k]);
				}
				node[j].clear();
				block[j] = 0;
			}

			for (int j = 0;j <= e.ss;j++) {
				adj[add].push_back(node[e.ff][0]);
				node[e.ff].erase(node[e.ff].begin());
			}
			block[e.ff] = node[e.ff].size();
		} else {
			for (int j = s.ss;j <= e.ss;j++) {
				adj[add].push_back(node[s.ff][s.ss]);
				node[s.ff].erase(node[s.ff].begin() + s.ss);
			}
			node[s.ff].insert(node[s.ff].begin() + s.ss, add);
			block[s.ff] = node[s.ff].size();
		}
		/*
		cout << add << ": ";
		for (int v:adj[add]) {
			cout << v << " ";
		}
		cout << endl;

		for (int i = 0;i < num;i++) {
			cout << "block " << i << " " << block[i] << endl;
			for (int j = 0;j < node[i].size();j++) cout << node[i][j] << " ";
			cout << endl;
		}
		*/
	}
	dfs(N + C - 1, -1);
	/*
	for (int i = N;i < N + C;i++) {
		cout << range[i].ff << " " << range[i].ss << endl;
	}
	*/
	for (int i = 0;i < N - 1;i++) sp[0][i] = a[i];
	for (int i = 1;i < 17;i++) {
		for (int j = 0;j < N - 1;j++) {
			sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1<<(i - 1))]);
		}
	}
	int an = 0, ap = 0;
	for (int i = N;i < N + C;i++) {
		int d = hbit(range[i].ss - range[i].ff) - 1;
		int val = max(sp[d][range[i].ff], sp[d][range[i].ss - (1<<d)]);
		//cout << range[i].ff << " " << range[i].ss - 1 << " " << val << endl;
		if (R > val) {
			if (dep[i] > an) {
				an = dep[i];
				ap = best[i];
			} else if (dep[i] == an) {
				ap = min(ap, best[i]);
			}
		}
	}

	return ap;
}
/*
int main() {
	io
	int n, c, r;
	cin >> n >> c >> r;
	int a[n - 1], s[c], e[c];
	for (int i = 0;i < n - 1;i++) cin >> a[i];
	for (int i = 0;i < c;i++) cin >> s[i] >> e[i];
	cout << GetBestPosition(n, c, r, a, s, e);
}
/*
5 3 3
1 0 2 4
1 3
0 1
0 1

10 5 5
7 3 2 4 6 8 0 1 9
0 1
4 7
2 3
1 3
0 2

 */

Compilation message (stderr)

tournament.cpp:167:1: warning: "/*" within comment [-Wcomment]
  167 | /*
      |  
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:86:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |    for (int j = s.ss;j < node[s.ff].size();j++) {
      |                      ~~^~~~~~~~~~~~~~~~~~~
tournament.cpp:71:31: warning: unused variable 'num' [-Wunused-variable]
   71 |  int blocksiz = int(sqrt(N)), num = (N - 1 + blocksiz) / blocksiz;
      |                               ^~~

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