Submission #121186

#	Time	Username	Problem	Language	Result	Execution time	Memory
121186		MAMBA	Jousting tournament (IOI12_tournament)	C++17	100 / 100	167 ms	41980 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

#define rep(i , j , k) for(int i = j; i < (int)k; i++)

constexpr int MAXN = 1e5 + 10;

struct node {
	node* par[20];
	int l, r;
	node(int l_, int r_) {
		rep(i , 0 , 20) par[i]= NULL;
		l = l_, r = r_;
	}
	void relax() {
		rep(i,  1 , 20)
			if (par[i - 1])
				par[i] = par[i - 1]->par[i - 1];
	}
};

node* a[MAXN];
node* b[MAXN];
node* state[MAXN << 1];
int cnt;

int seg[MAXN << 2];
int le[MAXN], ri[MAXN];

int segGet(int p , int l ,int r, int id = 1) {
	if (l == r - 1) return l;
	int mid = l + r >> 1;
	if (seg[id << 1] >= p) return segGet(p , l , mid ,id << 1);
	return segGet(p - seg[id << 1] , mid , r ,id << 1 | 1);
}

void segFlip(int p, int l , int r, int id = 1) {
	if (l == r - 1) {
		seg[id] ^= 1;
		return;
	}
	int mid = l + r >> 1;
	if (p < mid) segFlip(p , l , mid , id << 1);
	else segFlip(p , mid , r , id << 1 | 1);
	seg[id] = seg[id << 1] + seg[id << 1 | 1];
}

bool smax(int &l, int r) { 
	if (l < r) {
		l = r;
		return true;
	}
	return false;
}
bool smin(int &l, int r) { 
	if (l > r) {
		l = r;
		return true;
	}
	return false;
}


int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {

	rep(i , 0 , N) {
		segFlip(i , 0 , N);
		state[cnt++] = a[i] = b[i] = new node(i , i);
	}

	rep(i , 0 , C) {
		int s = S[i] + 1;
		int sz = E[i] - S[i] + 1;
		int last = -1, l = 1e9, r = -1;
		node * root = new node(-1 , -1);
		rep(z , 0 , sz) {
			last = segGet(s , 0 , N);
			smin(l , b[last]->l);
			smax(r , b[last]->r);
			b[last]->par[0] = root;
			segFlip(last , 0 , N);
		}
		segFlip(last , 0 , N);
		root->l = l;
		root->r = r;
		b[last] = root;
		state[cnt++] = root;
	}


	le[0] = -1e9;
	rep(i , 1 , N) {
		le[i] = le[i - 1];
		if (K[i - 1] > R)
			le[i] = i - 1;
	}
	ri[N - 1] = 1e9;
	for (int i = N - 2; ~i; i--) {
		ri[i] = ri[i  + 1];
		if (K[i] > R) ri[i] = i + 1;
	}

	for (int i = cnt - 1; ~i; i--)
		state[i]->relax();

	int pos = 0, res = -1;

	rep(i , 0 , N) {
		int local = 0;
		node * now = a[i];
		for (int j = 19; ~j; j--) {
			if (now->par[j] && now->par[j]->l > le[i] && now->par[j]->r < ri[i]) {
				local |= 1 << j;
				now = now->par[j];
			}
		}
		if (smax(res , local))
			pos = i;
	}	

	return pos;
}

Compilation message (stderr)

tournament.cpp: In function 'int segGet(int, int, int, int)':
tournament.cpp:33:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~
tournament.cpp: In function 'void segFlip(int, int, int, int)':
tournament.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid = l + r >> 1;
            ~~^~~

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