Submission #44238

#	Time	Username	Problem	Language	Result	Execution time	Memory
44238		baactree	Jousting tournament (IOI12_tournament)	C++17	49 / 100	95 ms	15908 KiB

tournament

#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 (stderr)

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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51