Submission #382735

#	Time	Username	Problem	Language	Result	Execution time	Memory
382735		alireza_kaviani	Jousting tournament (IOI12_tournament)	C++11	100 / 100	85 ms	23268 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define X				first
#define Y				second
#define sep				' '

const int MAXN = (1 << 18);
const int LOG = 18;

int n , m , r , ans[MAXN] , fen[MAXN] , nxt[MAXN] , val[MAXN] , dpl[MAXN] , dpr[MAXN],fen2[MAXN];
vector<int> vec[MAXN];
vector<pair<pii , pii>> Q[MAXN];

void add(int x , int val){
	for(x++ ; x < MAXN ; x += x & -x)	fen[x] += val;
}

int get(int x){
	int ans = 0;
	for(int i = (1 << (LOG - 1)) ; i ; i >>= 1){
		if(fen[ans + i] <= x){
			ans += i;
			x -= fen[ans];
		}
	}
	return ans;
}

void update(int x , int val){
	for(x += 2 ; x < MAXN ; x += x & -x)	fen2[x] += val;
}

int query(int x){
	int ans = 0;
	for(x += 2 ; x ; x -= x & -x)	ans += fen2[x];
	return ans;
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
	n = N; m = C; r = R;
	for(int i = 0 ; i < n - 1 ; i++){
		val[i] = K[i];
		nxt[i] = i + 1;
		add(i , 1);
	}
	add(n - 1 , 1);
	nxt[n - 1] = n;
	for(int i = 0 ; i < m ; i++){
		int l = S[i] , r = E[i];
		int cur = get(l) , tmp = cur;
		for(int j = 0 ; j < r - l + 1 ; j++){
			add(cur , -1);
			cur = nxt[cur];
		}
		nxt[tmp] = cur;
		add(tmp , 1);
		vec[tmp].push_back(cur - 1);
//		cout << tmp << sep << cur - 1 << endl;
	}
	//assert(fen[MAXN / 2] == 1);
	dpl[0] = -1;
	for(int i = 1 ; i < n ; i++){
		dpl[i] = dpl[i - 1];
		if(val[i - 1] > r)	dpl[i] = i - 1;
	}
	dpr[n - 1] = n - 1;
	for(int i = n - 2 ; i >= 0 ; i--){
		dpr[i] = dpr[i + 1];
		if(val[i] > r)	dpr[i] = i;
	}
	for(int i = 0 ; i < n ; i++){
		if(dpl[i] >= 0)	Q[dpl[i]].push_back({{i , -1} , {i - 1 , dpr[i]}});
		Q[i].push_back({{i , 1} , {i - 1 , dpr[i]}});
	}
	for(int i = 0 ; i < n ; i++){
//		cout << i << sep << dpl[i] << sep << dpr[i] << endl;
		for(int j : vec[i])	update(j , 1);
		for(auto &j : Q[i]){
			ans[j.X.X] += j.X.Y * (query(j.Y.Y) - query(j.Y.X));
		}
	}
	int res = 0;
	for(int i = 0 ; i < n ; i++){
		if(ans[i] > ans[res])	res = i;
	}
	return res;
}

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