Submission #310072

#	Time	Username	Problem	Language	Result	Execution time	Memory
310072		cheetose	Jousting tournament (IOI12_tournament)	C++17	100 / 100	82 ms	12924 KiB

tournament

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a))
#define MEM_1(a) memset((a),-1,sizeof(a))
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<db> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const int MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) { ll ret = 1; for (; b; b >>= 1, a = (a*a) % MMM)if (b & 1)ret = (ret*a) % MMM; return ret; }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };
int ddx[] = { -1,-2,1,-2,2,-1,2,1 }, ddy[] = { -2,-1,-2,1,-1,2,1,2 };

int a[100000];
int parent[100000];
Pi query[100000];
int find(int a)
{
	if (parent[a] < 0)return a;
	return parent[a] = find(parent[a]);
}
void merge(int a, int b)
{
	a = find(a), b = find(b);
	if (a != b)
	{
		parent[b] = a;
	}
}

int tree[262144];

void init(int node, int S, int E)
{
	if (S == E)
	{
		tree[node] = 1;
		return;
	}
	init(2 * node, S, (S + E) / 2);
	init(2 * node + 1, (S + E) / 2 + 1, E);
	tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void upd(int node, int S, int E, int k)
{
	tree[node]--;
	if (S == E)return;
	if (k <= (S + E) / 2)upd(node * 2, S, (S + E) / 2, k);
	else upd(node * 2 + 1, (S + E) / 2 + 1, E, k);
}

int findK(int node, int S, int E, int k)
{
	if (S == E)return S;
	if (k <= tree[node * 2])return findK(node * 2, S, (S + E) / 2, k);
	return findK(node * 2 + 1, (S + E) / 2 + 1, E, k - tree[node * 2]);
}

int T[100005];
int n,c,r;
void upd(int i, int k)
{
	i++;
	while (i <= n+1)
	{
		T[i] += k;
		i += (i&-i);
	}
}
int sum(int i)
{
	i++;
	int c = 0;
	while (i > 0)
	{
		c += T[i];
		i -= (i&-i);
	}
	return c;
}
int lg[100001],mx[100000][17];
int mm(int l,int r){
	int tt=lg[r-l+1];
	return max(mx[l][tt],mx[r-(1<<tt)+1][tt]);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	MEM_1(parent);
	fup(i,0,16,1)lg[1<<i]=i;
	fup(i,1,100000,1)if(!lg[i])lg[i]=lg[i-1];
	n=N,c=C,r=R;
	fup(i,0,n-2,1){
		a[i]=K[i];
		mx[i][0]=a[i];
	}
	fup(j,0,15,1){
		fup(i,0,n-2,1){
			if(i+(1<<(j+1))>=n)break;
			mx[i][j+1]=max(mx[i][j],mx[i+(1<<j)][j]);
		}
	}
	init(1,0,n-1);
	fup(i,0,c-1,1){
		int x=S[i],y=E[i];
		x++,y++;
		int l=findK(1,0,n-1,x),r=findK(1,0,n-1,y);
		query[i]=mp(find(l),r);
		while(find(l)!=find(r)){
			r=find(r);
			merge(r-1,r);
			upd(1,0,n-1,r-1);
		}
	}


	fup(i,0,c-1,1){
		auto [l,rr]=query[i];
		int t=mm(l,rr-1);
		if(r>t){
			upd(l,1);
			upd(rr+1,-1);
		}
	}
	int cc=-1,w=-1;
	fup(i,0,n-1,1){
		int t=sum(i);
		if(t>cc){
			cc=t;
			w=i;
		}
	}
	return w;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:118:2: note: in expansion of macro 'fup'
  118 |  fup(i,0,16,1)lg[1<<i]=i;
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:119:2: note: in expansion of macro 'fup'
  119 |  fup(i,1,100000,1)if(!lg[i])lg[i]=lg[i-1];
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:121:2: note: in expansion of macro 'fup'
  121 |  fup(i,0,n-2,1){
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:125:2: note: in expansion of macro 'fup'
  125 |  fup(j,0,15,1){
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:126:3: note: in expansion of macro 'fup'
  126 |   fup(i,0,n-2,1){
      |   ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:132:2: note: in expansion of macro 'fup'
  132 |  fup(i,0,c-1,1){
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:145:2: note: in expansion of macro 'fup'
  145 |  fup(i,0,c-1,1){
      |  ^~~
tournament.cpp:10:30: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
      |                              ^
tournament.cpp:154:2: note: in expansion of macro 'fup'
  154 |  fup(i,0,n-1,1){
      |  ^~~

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