oj.uz

Submission #44238

# Submission time Handle Problem Language Result Execution time Memory
44238 2018-03-30T16:58:22 Z baactree Jousting tournament (IOI12_tournament) C++17
49 / 100
 95 ms 15908 KB 
#include <bits/stdc++.h>
using namespace std;
int par[100005], sz[100005], tree[100005];
int ssz, mtree[400005];
int find(int x) {
	if (x == par[x])return x;
	return par[x] = find(par[x]);
}
void merge(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y)return;
	par[x] = y;
	sz[y] += sz[x];
}
void update(int idx, int val) {
	idx++;
	while (idx < 100005) {
		tree[idx] += val;
		idx += idx & (-idx);
	}
}
int query(int idx) {
	int ret = 0;
	idx++;
	while (idx) {
		ret += tree[idx];
		idx -= idx & (-idx);
	}
	return ret;
}
void mupdate(int idx, int val) {
	idx += ssz;
	while (idx) {
		mtree[idx] = max(mtree[idx], val);
		idx /= 2;
	}
}
int mquery(int le, int ri) {
	le += ssz;
	ri += ssz;
	int ret = 0;
	while (le <= ri) {
		if (le & 1)ret = max(ret, mtree[le++]);
		if (!(ri & 1))ret = max(ret, mtree[ri--]);
		le /= 2;
		ri /= 2;
	}
	return ret;
}
int s[100005], e[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for (int i = 0; i < N; i++) {
		par[i] = i;
		sz[i] = 1;
		if(i) update(i, 1);
	}
	for (int i = 0; i < C; i++) {
		int pre = -1;
		int le, ri, mid, st;
		le = 0; ri = N - 1;
		st = 0;
		while (le <= ri) {
			mid = (le + ri) / 2;
			if (query(mid) >= S[i]) {
				st = mid;
				ri = mid - 1;
			}
			else
				le = mid + 1;
		}
		s[i] = st;
		for (int j = S[i]; j <= E[i]; j++) {
			int ss = sz[find(st)];
			e[i] = st + ss - 1;
			if (pre != -1)merge(pre, st);
			pre = st;
			if (j != S[i])update(st, -1);
			st += ss;
		}
	}
	ssz = 1;
	while (ssz < N)ssz *= 2;
	for (int i = 0; i < N - 1; i++)
		mupdate(i, K[i]);
	mupdate(N - 1, 0x3f3f3f3f);
	vector<pair<int, int> > vec;
	for (int i = 0; i < C; i++) {
		if (mquery(s[i] + 1, e[i]) < R ||mquery(s[i], e[i] - 1) < R)
			vec.emplace_back(s[i], e[i]);
	}
	sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b) {
		if (a.second == b.second) {
			return a.first < b.first;
		}
		return a.second > b.second;
	});
	vector<int> lis;
	int ans = 0;
	int idx = 0;
	for (int i = 0; i < vec.size(); i++) {
		auto it = upper_bound(lis.begin(), lis.end(), vec[i].first);
		if (it == lis.end()) {
			lis.push_back(vec[i].first);
			ans = lis.size();
			idx = vec[i].first;
		}
		else {
			*it = vec[i].first;
			int len = it - lis.begin() + 1;
			if (ans < len || (ans == len && idx > vec[i].first)) {
				ans = len;
				idx = vec[i].first;
			}
		}
	}
	return idx;
}

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 416 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 752 KB Output is correct
5 Correct 3 ms 752 KB Output is correct
6 Correct 2 ms 752 KB Output is correct
7 Correct 3 ms 752 KB Output is correct
8 Correct 3 ms 752 KB Output is correct
9 Correct 2 ms 752 KB Output is correct
10 Correct 2 ms 868 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 868 KB Output is correct
2 Correct 7 ms 1032 KB Output is correct
3 Correct 3 ms 1100 KB Output is correct
4 Correct 6 ms 1184 KB Output is correct
5 Correct 6 ms 1248 KB Output is correct
6 Correct 5 ms 1308 KB Output is correct
7 Correct 6 ms 1388 KB Output is correct
8 Correct 6 ms 1444 KB Output is correct
9 Correct 3 ms 1508 KB Output is correct
10 Correct 8 ms 1532 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3392 KB Output is correct
2 Correct 88 ms 7236 KB Output is correct
3 Correct 31 ms 7600 KB Output is correct
4 Correct 88 ms 9768 KB Output is correct
5 Correct 81 ms 11168 KB Output is correct
6 Correct 95 ms 12100 KB Output is correct
7 Correct 90 ms 14272 KB Output is correct
8 Correct 83 ms 15908 KB Output is correct
9 Correct 28 ms 15908 KB Output is correct
10 Incorrect 32 ms 15908 KB Output isn't correct