Submission #284695

#	Time	Username	Problem	Language	Result	Execution time	Memory
284695		ChrisT	Jousting tournament (IOI12_tournament)	C++17	100 / 100	291 ms	23924 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;
template <typename t>
using pbds = tree<t,null_type,less<t>,rb_tree_tag,tree_order_statistics_node_update>;
const int MN = 2e5 + 5;
int GetBestPosition(int n, int c, int rnk, int *k, int *s, int *e) {
	vector<vector<int>> sp(__lg(n)+1,vector<int>(n));
	for (int i = 1; i < n; i++) sp[0][i] = k[i-1];
	for (int j = 1; j <= __lg(n); j++)
		for (int i = 1; i + (1 << j) - 1 < n; i++)
			sp[j][i] = max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
	auto query = [&] (int l, int r) {
		int lg = __lg(r-l+1);
		int ret = max(sp[lg][l],sp[lg][r-(1<<lg)+1]);
		return ret;
	};
	vector<vector<int>> st(n+1),ed(n+1); pbds<int> l,r;
	for (int i = 1; i <= n; i++) l.insert(i), r.insert(i);
	for (int i = 0; i < c; i++) {
		int sz = e[i] - s[i] + 1;
		int lb = *l.find_by_order(s[i]), rb = *r.find_by_order(e[i]);
		for (int j = 1; j < sz; j++) l.erase(l.find_by_order(s[i] + 1)), r.erase(r.find_by_order(e[i] - j));
		st[lb].emplace_back(rb); ed[rb].emplace_back(lb);
	}
	int cur = 0, best = -1, ret = -1;
	for (int i = 1; i <= n; i++) {
		for (int j : st[i]) if (query(i,j-1) < rnk) ++cur;
		if (cur > best) {
			best = cur;
			ret = i-1;
		}
		for (int j : ed[i]) if (query(j,i-1) < rnk) --cur; 
	}
	return ret;
}

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