Submission #645467

#	Time	Username	Problem	Language	Result	Execution time	Memory
645467		ymm	Jousting tournament (IOI12_tournament)	C++17	100 / 100	80 ms	22644 KiB

tournament

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 100'010;
int a[N];
int seg[N<<2];
int node[N];
vector<int> A[2*N];
int n, m;

void build(int i=0, int b=0, int e=n)
{
	seg[i] = e-b;
	if (e - b == 1) {
		node[b] = b;
		return;
	}
	build(2*i+1,b,(b+e)/2);
	build(2*i+2,(b+e)/2,e);
}

void up(int par, int l, int r, int skip=0, int i=0, int b=0, int e=n)
{
	if (r <= skip || skip+seg[i] <= l || seg[i]==0)
		return;
	if (e-b == 1) {
		A[par].push_back(node[b]);
		node[b] = skip == l? par: -1;
		seg[i] = skip == l? 1: 0;
		return;
	}
	up(par,l,r,skip+seg[2*i+1],2*i+2,(b+e)/2,e);
	up(par,l,r,skip,2*i+1,b,(b+e)/2);
	seg[i] = seg[2*i+1] + seg[2*i+2];
}

int cntr = 0;
int r;

pii mx[2*N];
pii maxpii(pii a, pii b)
{
	if (a.first > b.first)
		return {a.first, max(a.second, b.first)};
	else
		return {b.first, max(a.first, b.second)};
}
int h[2*N];
int par[2*N];
pii dfs(int v, int h)
{
	::h[v] = h;
	mx[v] = {-1, -1};
	if (v < n)
		mx[v] = {a[v], -1};
	for (int u : A[v]) {
		par[u] = v;
		mx[v] = maxpii(mx[v], dfs(u, h+1));
	}
	cntr += mx[v].first == r;
	return mx[v];
}

void up2(int v, int u)
{
	int x = mx[v].first;
	while (h[u] > h[v]) {
		cntr -= mx[u].first == r;
		u = par[u];
	}
	while (h[v] > h[u]) {
		if (mx[v].first < r || mx[v].first==x && mx[v].second < r) {
			mx[v].first = r;
			++cntr;
		}
		v = par[v];
	}
	while (v != u)
	{
		if (mx[v].first < r || mx[v].first==x && mx[v].second < r) {
			mx[v].first = r;
			++cntr;
		}
		cntr -= mx[u].first == r;
		v = par[v];
		u = par[u];
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	m = n = N;
	Loop (i,0,n-1)
		a[i] = K[i];
	r = a[n-1] = R;
	build();
	Loop (i,0,C)
		up(m++, S[i], E[i]+1);
	dfs(m-1, 0);
	int mx = cntr, mxp = n-1;
	LoopR (i,0,n-1) {
		up2(i, i+1);
		if (cntr >= mx) {
			mx = cntr;
			mxp = i;
		}
	}
	return mxp;
}

Compilation message (stderr)

tournament.cpp: In function 'void up2(int, int)':
tournament.cpp:77:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   77 |   if (mx[v].first < r || mx[v].first==x && mx[v].second < r) {
      |                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
tournament.cpp:85:41: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   85 |   if (mx[v].first < r || mx[v].first==x && mx[v].second < r) {
      |                          ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

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