Submission #1015572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015572		parsadox2	Jousting tournament (IOI12_tournament)	C++17	100 / 100	58 ms	19268 KiB

tournament

#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;

const int N = 1e5 + 10 , Lg = 17;

int n , ar[N] , c , R , l[N] , r[N] , rmq[N][Lg] , lg[N];

struct SEG1{
	int sum[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		sum[node] = nr - nl;
		if(nl + 1 == nr)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);
		Build(rc , mid , nr);
	}
	void Zero(int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			sum[node] = 0;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Zero(l , r , lc , nl , mid);  Zero(l , r , rc , mid , nr);
		sum[node] = sum[lc] + sum[rc];
	}
	int Get(int val , int node = 1 , int nl = 0 , int nr = n)
	{
		if(nl + 1 == nr)
			return nl;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		if(val <= sum[lc])
			return Get(val , lc , nl , mid);
		return Get(val - sum[lc] , rc , mid , nr);
	}
} sl , sr;

struct SEG{
	pair <int , int> mx[N << 2];
	int lzy[N << 2];
	void Build(int node = 1 , int nl = 0 , int nr = n)
	{
		mx[node] = make_pair(0 , -nl);
		if(nl + 1 == nr)
			return;
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Build(lc , nl , mid);
		Build(rc , mid , nr);
	}
	void Shift(int node , int lc , int rc)
	{
		if(lzy[node] == 0)
			return;
		mx[lc].F += lzy[node];
		mx[rc].F += lzy[node];
		lzy[lc] += lzy[node];
		lzy[rc] += lzy[node];
		lzy[node] = 0;
	}
	void Add(int l , int r , int node = 1 , int nl = 0 , int nr = n)
	{
		if(r <= nl || nr <= l)
			return;
		if(l <= nl && nr <= r)
		{
			mx[node].F++;
			lzy[node]++;
			return;
		}
		int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
		Add(l , r , lc , nl , mid);
		Add(l , r , rc , mid , nr);
		mx[node] = max(mx[lc] , mx[rc]);
	}
} seg;

int Get_mx(int l , int r)
{
	int tmp = lg[r - l];
	return max(rmq[l][tmp] , rmq[r - (1 << tmp)][tmp]);
}

int GetBestPosition(int nn , int cc , int rr , int *kk , int *ss , int *ee)
{
	n = nn;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		ar[i] = kk[i];
		rmq[i][0] = ar[i];
	}
	c = cc;   R = rr;
	for(int i = 0 ; i < c ; i++)
	{
		l[i] = ss[i];
		r[i] = ee[i];
	}
	lg[1] = 0;
	for(int i = 2 ; i < N ; i++)
		lg[i] = lg[i / 2] + 1;
	for(int i = 1 ; i < Lg ; i++)  for(int j = 0 ; j + (1 << i) < n ; j++)
		rmq[j][i] = max(rmq[j][i - 1] , rmq[j + (1 << (i - 1))][i - 1]);
	sl.Build();
	sr.Build();
	seg.Build();
	for(int i = 0 ; i < c ; i++)
	{
		l[i] = sl.Get(l[i] + 1);
		r[i] = sr.Get(r[i] + 1);
		sl.Zero(l[i] + 1 , r[i] + 1);
		sr.Zero(l[i] , r[i]);
		int mx = Get_mx(l[i] , r[i]);
		if(mx < R)
			seg.Add(l[i] , r[i] + 1);
	}
	return abs(seg.mx[1].S);
}

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