Submission #1012093

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012093		AmirAli_H1	Jousting tournament (IOI12_tournament)	C++17	100 / 100	130 ms	18512 KiB

tournament

// In the name of Allah

#include <bits/stdc++.h>
using namespace std;

typedef		long long int			ll;
typedef		long double				ld;
typedef		pair<int, int>			pii;
typedef		pair<ll, ll>			pll;
typedef		complex<ld>				cld;

#define		all(x)					(x).begin(),(x).end()
#define		len(x)					((ll) (x).size())
#define		F						first
#define		S						second
#define		pb						push_back
#define		sep						' '
#define		endl					'\n'
#define		Mp						make_pair
#define		kill(x)					cout << x << '\n', exit(0)
#define		set_dec(x)				cout << fixed << setprecision(x);
#define		file_io(x,y)			freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n, q, x;
const int maxn = (1 << 17) + 4;
int a[maxn], ok[maxn]; pii Q[maxn];
int t[2 * maxn]; set<pii> st;
int tx[maxn]; set<int> stx;
vector<int> A1[maxn], A2[maxn];

void build(int v, int tl, int tr) {
	if (tr - tl == 1) {
		t[v] = 1;
		return ;
	}
	int mid = (tl + tr) / 2;
	build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
	t[v] = t[2 * v + 1] + t[2 * v + 2];
}

void set_val(int v, int tl, int tr, int i, int x) {
	if (i >= tr || i < tl) return ;
	if (tr - tl == 1) {
		t[v] = x;
		return ;
	}
	int mid = (tl + tr) / 2;
	set_val(2 * v + 1, tl, mid, i, x); set_val(2 * v + 2, mid, tr, i, x);
	t[v] = t[2 * v + 1] + t[2 * v + 2];
}

int get_ind(int v, int tl, int tr, int x) {
	if (tr - tl == 1) {
		if (t[v] == 1) return tl;
		else return tr;
	}
	int mid = (tl + tr) / 2;
	if (t[2 * v + 1] >= x) return get_ind(2 * v + 1, tl, mid, x);
	else return get_ind(2 * v + 2, mid, tr, x - t[2 * v + 1]);
}

void addx(int i, int x) {
	for (++i; i < maxn; i += (i & -i)) tx[i] += x;
}

int getx(int i) {
	int res = 0;
	for (++i; i > 0; i -= (i & -i)) res += tx[i];
	return res;
}

int GetBestPosition(int Nx, int Cx, int Rx, int Kx[], int Sx[], int Ex[]) {
	n = Nx; q = Cx; x = Rx;
	for (int i = 0; i < n - 1; i++) a[i] = (Kx[i] > x);
	for (int i = 0; i < q; i++) Q[i] = Mp(Sx[i], Ex[i]);
	
	build(0, 0, n);
	for (int i = 0; i < n; i++) st.insert(Mp(i, 1));
	
	for (int i = 0; i < q; i++) {
		int l = Q[i].F, r = Q[i].S;
		l = get_ind(0, 0, n, l + 1); r = get_ind(0, 0, n, r + 2) - 1;
		int x = 0; Q[i] = Mp(l, r);
		while (true) {
			auto it = st.lower_bound(Mp(l, -1));
			if (it == st.end() || (*it).F > r) break;
			pii f = *it; x += f.S;
			st.erase(f); set_val(0, 0, n, f.F, 0);
		}
		st.insert(Mp(l, x)); set_val(0, 0, n, l, 1);
	}
	
	for (int i = 0; i < n - 1; i++) {
		if (a[i] == 1) stx.insert(i);
	}
	for (int i = 0; i < q; i++) {
		int l = Q[i].F, r = Q[i].S;
		A1[l].pb(i); A2[r].pb(i);
		auto it = stx.lower_bound(l);
		if (it != stx.end() && (*it) < r) ok[i] = 0;
		else ok[i] = 1;
	}
	
	pii res = Mp(-1, -1); stx.clear();
	for (int i = 0; i < n; i++) {
		for (int j : A1[i]) {
			if (!ok[j]) stx.insert(j);
			else addx(j, 1);
		}
		
		int ind = q - 1;
		if (!stx.empty()) ind = (*stx.begin()) - 1;
		int x = getx(ind);
		if (x > res.F) res = Mp(x, i);
		
		for (int j : A2[i]) {
			if (!ok[j]) stx.erase(j);
			else addx(j, -1);
		}
	}
	
	return res.S;
}

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