oj.uz

Submission #381865

# Submission time Handle Problem Language Result Execution time Memory
381865 2021-03-26T05:55:30 Z pavement Jousting tournament (IOI12_tournament) C++17
100 / 100
 187 ms 13036 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2796 KB Output is correct
2 Correct 9 ms 3180 KB Output is correct
3 Correct 6 ms 3180 KB Output is correct
4 Correct 9 ms 3180 KB Output is correct
5 Correct 8 ms 3180 KB Output is correct
6 Correct 8 ms 3180 KB Output is correct
7 Correct 9 ms 3180 KB Output is correct
8 Correct 8 ms 3180 KB Output is correct
9 Correct 5 ms 3180 KB Output is correct
10 Correct 11 ms 3180 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 7532 KB Output is correct
2 Correct 183 ms 13036 KB Output is correct
3 Correct 96 ms 11620 KB Output is correct
4 Correct 170 ms 12908 KB Output is correct
5 Correct 168 ms 12396 KB Output is correct
6 Correct 187 ms 12396 KB Output is correct
7 Correct 176 ms 12908 KB Output is correct
8 Correct 173 ms 12908 KB Output is correct
9 Correct 84 ms 11624 KB Output is correct
10 Correct 100 ms 11244 KB Output is correct