oj.uz

Submission #242238

# Submission time Handle Problem Language Result Execution time Memory
242238 2020-06-27T07:19:39 Z shenxy Jousting tournament (IOI12_tournament) C++11
100 / 100
 257 ms 42272 KB 
#include <algorithm>
#include <vector>
#include <map>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define F first
#define S second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> os;
typedef pair<int, int> ii;
int* arr;
struct seg {
	int s, e, m, v;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e, m = (s + e) / 2;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
			v = max(l -> v, r -> v);
		} else v = arr[s];
	}
	int query(int a, int b) {
		if (s == a && e == b) return v;
		if (a > m) return r -> query(a, b);
		if (b <= m) return l -> query(a, b);
		return max(l -> query(a, m), r -> query(m + 1, b));
	}
} *root;
vector<int> adjlist[199999];
ii range[199999];
void dfs(int v) {
	if (adjlist[v].size() != 0) {
		range[v] = ii(100000, -1);
		for (int i: adjlist[v]) dfs(i);
		for (int i: adjlist[v]) range[v].F = min(range[v].F, range[i].F), range[v].S = max(range[v].S, range[i].S);
	} else range[v] = ii(v, v);
}
ii dp(int v, int R) {
	if (adjlist[v].size() != 0) {
		ii ans = ii(-100000, 1);
		for (int i: adjlist[v]) ans = max(ans, dp(i, R));
		if (root -> query(range[v].F, range[v].S - 1) < R) ++ans.F;
		return ans;
	} else return ii(0, -v);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	os sets;
	map<int, int> mp;
	for (int i = 0; i < N; ++i) sets.insert(i);
	for (int i = 0; i < N; ++i) mp[i] = i;
	for (int i = 0; i < C; ++i) {
		int x = *sets.find_by_order(S[i]);
		adjlist[N + i].push_back(mp[x]);
		for (int j = S[i]; j < E[i]; ++j) {
			os::iterator it = sets.find_by_order(S[i] + 1);
			adjlist[N + i].push_back(mp[*it]);
			sets.erase(it);
		}
		mp[x] = N + i;
	}
	arr = K;
	root = new seg(0, N - 2);
	dfs(N + C - 1);
	return -dp(N + C - 1, R).S;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 15 ms 6912 KB Output is correct
3 Correct 11 ms 5888 KB Output is correct
4 Correct 14 ms 6272 KB Output is correct
5 Correct 14 ms 6528 KB Output is correct
6 Correct 16 ms 6016 KB Output is correct
7 Correct 14 ms 6656 KB Output is correct
8 Correct 14 ms 6400 KB Output is correct
9 Correct 11 ms 5760 KB Output is correct
10 Correct 16 ms 6144 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 14840 KB Output is correct
2 Correct 238 ms 42272 KB Output is correct
3 Correct 140 ms 21624 KB Output is correct
4 Correct 210 ms 31864 KB Output is correct
5 Correct 208 ms 35192 KB Output is correct
6 Correct 257 ms 23928 KB Output is correct
7 Correct 219 ms 35320 KB Output is correct
8 Correct 219 ms 35448 KB Output is correct
9 Correct 126 ms 21496 KB Output is correct
10 Correct 153 ms 21496 KB Output is correct