Submission #63315

#	Time	Username	Problem	Language	Result	Execution time	Memory
63315		chpipis	Jousting tournament (IOI12_tournament)	C++11	100 / 100	187 ms	29156 KiB

tournament

#ifndef EVAL
#include "grader.h"
#endif
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define fi first
#define se second

typedef pair<int, int> ii;

const int LOGN = 19;
const int MAXN = 1e5 + 5;

int n;
int to[LOGN][MAXN * 2];
int spt[LOGN][MAXN];
int lg[MAXN];
ii seg[MAXN];
int bit[MAXN];

#define lsone(s) (s & (-s))

void add(int b, int val) {
	b++;
	while (b < MAXN) {
		bit[b] += val;
		b += lsone(b);
	}
}

int getkth(int k) {
	k++;
	int pos = 0;
	for (int j = LOGN - 1; j >= 0; j--) {
		if (pos + (1 << j) < MAXN and bit[pos + (1 << j)] < k) {
			k -= bit[pos + (1 << j)];
			pos += (1 << j);
		}
	}
	return pos;
}

inline int query(int a, int b) {
	if (a > b) return 0;
	if (b < 0 || a >= n)
		return 0;
	int log = lg[b - a + 1];
	return max(spt[log][a], spt[log][b - (1 << log) + 1]);
}

int GetBestPosition(int _n, int c, int r, int k[], int s[], int e[]) {
	n = _n;
	for (int i = 2; i < MAXN; i++)
		lg[i] = lg[i >> 1] + 1;
	memset(bit, 0, sizeof bit);
	map<int, int> active;
	for (int i = 0; i < n; i++) {
		add(i, +1);
		seg[i] = mp(i, i);
		active[i] = i;
	}
	memset(to, -1, sizeof to);
	for (int i = 0; i < c; i++) {
		int a = getkth(s[i]);
		int b = getkth(e[i]);
		s[i] = seg[a].fi;
		e[i] = seg[b].se;
		seg[a] = mp(s[i], e[i]);
		to[0][active[a]] = n + i;
		for (auto it = active.lower_bound(b); it->fi != a; it = prev(it)) {
			to[0][it->se] = n + i;
			add(it->fi, -1);
			it = active.erase(it);
		}
		active[a] = n + i;
	}
	for (int j = 1; j < LOGN; j++) {
		for (int i = 0; i < n + c; i++) {
			if (to[j - 1][i] != -1)
				to[j][i] = to[j - 1][to[j - 1][i]];
		}
	}
	spt[0][n - 1] = 0;
	for (int i = 0; i < n - 1; i++) {
		spt[0][i] = k[i];
	}
	for (int j = 1; j < LOGN; j++) {
		for (int i = 0; i + (1 << j) <= n; i++) {
			spt[j][i] = max(spt[j - 1][i], spt[j - 1][i + (1 << (j - 1))]);
		}
	}
	int ans = -1;
	int pos = -1;
	for (int i = 0; i < n; i++) {
		int cur = 0, who = i;
		for (int j = LOGN - 1; j >= 0; j--) {
			if (to[j][who] != -1) {
				int nxt = to[j][who] - n;
				int val = query(s[nxt], e[nxt] - 1);
				if (val <= r) {
					who = nxt + n;
					cur += (1 << j);
				}
			}
		}
		if (cur > ans) {
			ans = cur;
			pos = i;
		}
	}
	return pos;
}

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