Submission #419264

#	Time	Username	Problem	Language	Result	Execution time	Memory
419264		arayi	Jousting tournament (IOI12_tournament)	C++17	100 / 100	270 ms	9804 KiB

tournament

#include <iostream>
#include <vector>
#define ad push_back
#define MP make_pair
#define fr first
#define sc second
#define pir pair<int, int>
using namespace std;

const int N = 1e6 + 30;
int n, m;
int l[N], r[N], a[N];

int t[4 * N];
pir flg[4 * N];
void push(int nd)
{
	if (flg[nd].fr > 0)
	{
		t[nd] = flg[nd].fr + flg[nd].sc;
		flg[nd * 2] = flg[nd * 2 + 1] = flg[nd];
		flg[nd] = MP(0, 0);
	}
	else
	{
		t[nd] += flg[nd].sc;
		flg[nd * 2].sc += flg[nd].sc;
		flg[nd * 2 + 1].sc += flg[nd].sc;
		flg[nd].sc = 0;
	}
}
void upd(int l, int r, int v, int nl = 1, int nr = n, int nd = 1)
{
	push(nd);
	if (l > nr || r < nl) return;
	if (l == nl && r == nr)
	{
		if (v > 0) flg[nd] = MP(v, 0);
		else flg[nd].sc += v;
		push(nd);
		return;
	}
	int mid = (nl + nr) / 2;
	upd(l, min(mid, r), v, nl, mid, nd * 2);
	upd(max(mid + 1, l), r, v, mid + 1, nr, nd * 2 + 1);
	t[nd] = min(t[nd * 2], t[nd * 2 + 1]);
}
int qry(int v, int l = 1, int r = n, int nd = 1)
{
	push(nd);
	if (l == r)
	{
		if (t[nd] > v) return l - 1;
		return l;
	}
	push(nd * 2);
	push(nd * 2 + 1);
	int mid = (l + r) / 2;
	if (t[nd * 2 + 1] <= v) return qry(v, mid + 1, r, nd * 2 + 1);
	else return qry(v, l, mid, nd * 2);
}
int qr(int q, int l = 1, int r = n, int nd = 1)
{
	push(nd);
	if (l > q || r < q) return 0;
	if (l == r) return t[nd];
	int mid = (l + r) / 2;
	return qr(q, l, mid, nd * 2) + qr(q, mid + 1, r, nd * 2 + 1);
}
void bld(int l = 0, int r = n - 2, int nd = 1)
{
	if (l == r)
	{
		t[nd] = a[l];
		return;
	}
	int mid = (l + r) / 2;
	bld(l, mid, nd * 2);
	bld(mid + 1, r, nd * 2 + 1);
	t[nd] = max(t[nd * 2], t[nd * 2 + 1]);
}
int qry1(int l, int r, int nl = 0, int nr = n - 2, int nd = 1)
{
	if (l > nr || r < nl) return 0;
	if (l == nl && r == nr) return t[nd];
	int mid = (nl + nr) / 2;
	return max(qry1(l, min(mid, r), nl, mid, nd * 2), qry1(max(mid + 1, l), r, mid + 1, nr, nd * 2 + 1));
}
int fp[N];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) 
{
	n = N, m = C;
	for (int i = 1; i <= n; i++) upd(i, i, i);
	for (int i = 0; i < n - 1; i++) a[i] = K[i];
	for (int i = 0; i < m; i++)
	{
		S[i]++, E[i]++;
		int a = qry(S[i] - 1) + 1, b = qry(E[i]);
		l[i] = a - 1, r[i] = b - 1;
		upd(a, b, S[i]);
		upd(b + 1, n, S[i] - E[i]);
		S[i]--, E[i]--;
	}
	bld();
	for (int i = 0; i < m; i++)
	{
		int sm = qry1(l[i], r[i] - 1);
		//cout << l[i] << " " << r[i] << " " << sm << endl;
		if (sm < R) fp[l[i]]++, fp[r[i] + 1]--;
	}
	int i1 = 0; 
	for (int i = 1; i < n; i++)
	{
		fp[i] += fp[i - 1];
		if (fp[i] > fp[i1]) i1 = i;
	}
	return i1;
}

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