Submission #381865

#	Time	Username	Problem	Language	Result	Execution time	Memory
381865		pavement	Jousting tournament (IOI12_tournament)	C++17	100 / 100	187 ms	13036 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
//#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
int N, link[100005], sz[100005], lft[100005], rig[100005], nr[100005], ft[100005], ans[100005];
vector<int> st[100005];
multiset<int> segs;
ordered_set comp;
 
inline int ls(int x) { return x & -x; }
 
int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}
 
void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	lft[a] = min(lft[a], lft[b]);
	rig[a] = max(rig[a], rig[b]);
	link[b] = a;
}
 
void upd(int p, int v) {
	for (p++; p <= N; p += ls(p)) ft[p] += v;
}
 
int qry(int p) {
	int r = 0;
	for (p++; p; p -= ls(p)) r += ft[p];
	return r;
}
 
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	::N = N;
	for (int i = 0; i < N; i++) {
		link[i] = lft[i] = rig[i] = i;
		sz[i] = 1;
		comp.insert(i);
	}
	int frnt = 0, bk = 0, bkg = N;
	ii ret;
	for (int i = N - 2; i >= 0; i--)
		if (K[i] > R) {
			bkg = i;
			break;
		}
	nr[N] = 1e9;
	for (int i = N - 1; i >= 0; i--) {
		if (K[i] > R) nr[i] = i + 1;
		else nr[i] = nr[i + 1];
	}
	for (int i = 0; i < C; i++) {
		vector<ordered_set::iterator> del;
		auto it = comp.find_by_order(S[i]);
		del.pb(it);
		for (int j = 0; j < E[i] - S[i]; j++) {
			int tmp = *it;
			++it;
			del.pb(it);
			unite(tmp, *it);
		}
		for (auto j : del) comp.erase(j);
		comp.insert(find(*it));
		S[i] = lft[find(*it)];
		E[i] = rig[find(*it)];
		if (S[i] == 0 && nr[0] > E[i]) frnt++;
		if (E[i] == N - 1 && S[i] > bkg) bk++;
		st[S[i]].pb(E[i]);
	}
	for (int j : st[0]) {
		if (!j) continue;
		upd(j, 1);
		segs.insert(j);
	}
	ret = max(mp(frnt, 0), mp(bk, -(N - 1)));
	for (int i = 1; i < N - 1; i++) {
		if (K[i - 1] > R) {
			for (int j : segs) upd(j, -1);
			segs.clear();
		}
		for (int j : st[i]) {
			segs.insert(j);
			upd(j, 1);
		}
		ans[i] = qry(min(N - 1, nr[i] - 1));
		ret = max(ret, mp(ans[i], -i));
		while (!segs.empty() && *segs.begin() == i) {
			upd(*segs.begin(), -1);
			segs.erase(segs.begin());
		}
	}
	return -ret.second;
}

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