oj.uz

Submission #645467

# Submission time Handle Problem Language Result Execution time Memory
645467 2022-09-27T08:02:37 Z ymm Jousting tournament (IOI12_tournament) C++17
100 / 100
 80 ms 22644 KB 
#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5076 KB Output is correct
4 Correct 3 ms 5016 KB Output is correct
5 Correct 3 ms 5016 KB Output is correct
6 Correct 3 ms 5016 KB Output is correct
7 Correct 3 ms 5020 KB Output is correct
8 Correct 3 ms 5076 KB Output is correct
9 Correct 3 ms 4948 KB Output is correct
10 Correct 3 ms 4948 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5020 KB Output is correct
2 Correct 5 ms 5844 KB Output is correct
3 Correct 4 ms 5288 KB Output is correct
4 Correct 6 ms 5664 KB Output is correct
5 Correct 5 ms 5612 KB Output is correct
6 Correct 5 ms 5412 KB Output is correct
7 Correct 6 ms 5716 KB Output is correct
8 Correct 6 ms 5588 KB Output is correct
9 Correct 4 ms 5204 KB Output is correct
10 Correct 6 ms 5460 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 9240 KB Output is correct
2 Correct 80 ms 22644 KB Output is correct
3 Correct 20 ms 10216 KB Output is correct
4 Correct 71 ms 18380 KB Output is correct
5 Correct 68 ms 19660 KB Output is correct
6 Correct 56 ms 13488 KB Output is correct
7 Correct 71 ms 19780 KB Output is correct
8 Correct 77 ms 19780 KB Output is correct
9 Correct 15 ms 9804 KB Output is correct
10 Correct 20 ms 10188 KB Output is correct