oj.uz

Submission #63315

# Submission time Handle Problem Language Result Execution time Memory
63315 2018-08-01T11:02:17 Z chpipis Jousting tournament (IOI12_tournament) C++11
100 / 100
 187 ms 29156 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 15992 KB Output is correct
2 Correct 16 ms 16152 KB Output is correct
3 Correct 16 ms 16152 KB Output is correct
4 Correct 14 ms 16164 KB Output is correct
5 Correct 15 ms 16212 KB Output is correct
6 Correct 17 ms 16288 KB Output is correct
7 Correct 15 ms 16288 KB Output is correct
8 Correct 16 ms 16288 KB Output is correct
9 Correct 19 ms 16288 KB Output is correct
10 Correct 15 ms 16288 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 16288 KB Output is correct
2 Correct 25 ms 16748 KB Output is correct
3 Correct 22 ms 16800 KB Output is correct
4 Correct 21 ms 16956 KB Output is correct
5 Correct 25 ms 16956 KB Output is correct
6 Correct 22 ms 16956 KB Output is correct
7 Correct 21 ms 16956 KB Output is correct
8 Correct 28 ms 16956 KB Output is correct
9 Correct 18 ms 16956 KB Output is correct
10 Correct 28 ms 16956 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 22424 KB Output is correct
2 Correct 187 ms 29156 KB Output is correct
3 Correct 117 ms 29156 KB Output is correct
4 Correct 146 ms 29156 KB Output is correct
5 Correct 161 ms 29156 KB Output is correct
6 Correct 181 ms 29156 KB Output is correct
7 Correct 145 ms 29156 KB Output is correct
8 Correct 148 ms 29156 KB Output is correct
9 Correct 79 ms 29156 KB Output is correct
10 Correct 115 ms 29156 KB Output is correct