Submission #17138

#	Time	Username	Problem	Language	Result	Execution time	Memory
17138		erdemkiraz	Jousting tournament (IOI12_tournament)	C++98	0 / 100	36 ms	11540 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 1 << 17;

int fen[N], t[N << 1];

void up(int x, int k) {
	x++;
	for(; x < N; x += x & -x)
		fen[x] += k;
}

int get(int x) {
	x++;
	int sum = 0;
	for(; x; x -= x & -x)
		sum += fen[x];
	return sum;
}

int getMax(int l, int r) {
	int ans = 0;
	for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
		if(l & 1) ans = max(ans, t[l]);
		if(~r & 1) ans = max(ans, t[r]);
	}
	return ans;
}

vector < int > v[N << 1];

void add(int x, int l, int r, int x1, int x2, int k) {
	if(r < x1 or x2 < l)
		return;
	if(x1 <= l and r <= x2) {
		//printf("x = %d k = %d\n", x, k);
		v[x].push_back(k);
		return;
	}
	int m = l + r >> 1;
	add(x + x, l, m, x1, x2, k);
	add(x + x + 1, m + 1, r, x1, x2, k);
}

int me;
int sz = 0;
int ans = -inf, best = -1;
int mx[N];

void solve(int x, int l, int r) {
	foreach(it, v[x]) {
		int u = *it;
		//printf("u geldiiiiiiiiiiiiiiiiii = %d\n", u);
		int last = sz ? mx[sz - 1] : 0;
		mx[sz++] = max(last, u);
	}
	if(l == r) {
		int k = -1;
		if(sz and mx[0] < me) {
			int l = 0, r = sz - 1;
			while(l + 1 < r) {
				int m = l + r >> 1;
				if(mx[m] < me) {
					l = m;
				}
				else {
					r = m - 1;
				}
			}
			if(mx[r] < me)
				l = r;
			k = l;
		}
		//for(int i = 0; i < sz; i++)
		//	printf("mx_i = %d\n", mx[i]);
		//printf("me = %d\n",me);
		//printf("l = %d k = %d\n", l, k);
		//puts("");
		if(k > ans) {
			ans = k;
			best = l;
		}
	}
	else {
		int m = l + r >> 1;
		solve(x + x, l, m);
		solve(x + x + 1, m + 1, r);
		sz -= v[x].size();
	}
	sz -= v[x].size();
}

int GetBestPosition(int n, int m, int me, int a[], int L[], int R[]) {
	:: me = me;
	for(int i = 0; i < m; i++) {
		int x = R[i] - L[i];
		L[i] = get(L[i]) + L[i];
		R[i] = get(R[i]) + R[i];
		up(L[i], x);
		//printf("%d %d\n", L[i], R[i]);
	}
	for(int i = 0; i < n; i++)
		t[i + N] = a[i];
	for(int i = N - 1; i >= 1; i--)
		t[i] = max(t[i + i], t[i + i + 1]);
	for(int i = 0; i < m; i++) {
		int l = L[i];
		int r = R[i] - 1;
		int res = getMax(l, r);
		add(1, 0, n - 1, L[i], R[i], res);
		//printf("l = %d r = %d res = %d\n", l, r, res);
	}
	solve(1, 0, n - 1);
	assert(best != -1);
	return best;
}

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