oj.uz

Submission #121186

# Submission time Handle Problem Language Result Execution time Memory
121186 2019-06-26T07:44:23 Z MAMBA Jousting tournament (IOI12_tournament) C++17
100 / 100
 167 ms 41980 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 2 ms 512 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 640 KB Output is correct
2 Correct 8 ms 2432 KB Output is correct
3 Correct 5 ms 1536 KB Output is correct
4 Correct 8 ms 2432 KB Output is correct
5 Correct 8 ms 2176 KB Output is correct
6 Correct 8 ms 2048 KB Output is correct
7 Correct 8 ms 2432 KB Output is correct
8 Correct 9 ms 2432 KB Output is correct
9 Correct 5 ms 1536 KB Output is correct
10 Correct 9 ms 2432 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 17144 KB Output is correct
2 Correct 167 ms 41976 KB Output is correct
3 Correct 72 ms 23928 KB Output is correct
4 Correct 150 ms 41848 KB Output is correct
5 Correct 152 ms 40312 KB Output is correct
6 Correct 153 ms 34940 KB Output is correct
7 Correct 166 ms 41920 KB Output is correct
8 Correct 159 ms 41980 KB Output is correct
9 Correct 65 ms 22648 KB Output is correct
10 Correct 88 ms 23672 KB Output is correct