oj.uz

Submission #17140

# Submission time Handle Problem Language Result Execution time Memory
17140 2015-11-06T17:20:33 Z erdemkiraz Jousting tournament (IOI12_tournament) C++
100 / 100
 574 ms 30456 KB 
#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 t[N << 1];

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;
}

int n, m, me;
vector < ii > v[N << 1];

namespace tree{
	ii t[N << 1];
	ii merge(ii x, ii y) {
		return ii(max(x.first, y.first), x.second + y.second);
	}
	void add(int x, int l, int r, int x1, int k) {
		if(l == r) {
			if(k == -1)
				t[x] = ii(0, 0);
			else
				t[x] = ii(k, 1);
			return;
		}
		int m = l + r >> 1;
		if(x1 <= m)
			add(x + x, l, m, x1, k);
		else
			add(x + x + 1, m + 1, r, x1, k);
		t[x] = merge(t[x + x], t[x + x + 1]);
	}
	int get(int x, int l, int r, int k) {
		if(l == r) {
			return t[x].first < me;
		}
		int m = l + r >> 1;
		if(t[x + x].first < me) {
			return t[x + x].second + get(x + x + 1, m + 1, r, k);
		}
		return get(x + x, l, m, k);
	}
}

int curTime;

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) {
		v[x].push_back(ii(k, curTime));
		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 ans = -inf, best = -1;

void solve(int x, int l, int r) {
	foreach(it, v[x]) {
		int u = it -> first;
		int t = it -> second;
		//printf("add %d %d\n", t, u);
		tree :: add(1, 0, m - 1, t, u);
	}
	if(l == r) {
		int k = tree :: get(1, 0, m - 1, me);
		//printf("l = %d k = %d\n", l, k);
		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);
	}
	foreach(it, v[x]) {
		int u = it -> first;
		int t = it -> second;
		//printf("del %d %d\n", t, u);
		tree :: add(1, 0, m - 1, t, -1);
	}
}

namespace makeT{
	ii a[N];
	int t[N << 1];
	void init(int x, int l, int r) {
		if(l == r) {
			t[x] = 1;
			return;
		}
		int m = l + r >> 1;
		init(x + x, l, m);
		init(x + x + 1, m + 1, r);
		t[x] = t[x + x] + t[x + x + 1];
	}
	void init() {
		for(int i = 0; i < n; i++)
			a[i] = ii(i, i);
		init(1, 0, n - 1);
	}
	void del(int x, int l, int r, int x1, int x2) {
		if(r < x1 or x2 < l or !t[x])
			return;
		if(x1 <= l and r <= x2) {
			t[x] = 0;
			return;
		}
		int m = l + r >> 1;
		del(x + x, l, m, x1, x2);
		del(x + x + 1, m + 1, r, x1, x2);
		t[x] = t[x + x] + t[x + x + 1];
	}
	void up(int l, int r) {
		a[l] = ii(l, r);
		del(1, 0, n - 1, l + 1, r);
	}
	int get(int x, int l, int r, int k) {
		if(l == r)
			return l;
		int m = l + r >> 1;
		if(t[x + x] >= k)
			return get(x + x, l, m, k);
		return get(x + x + 1, m + 1, r, k - t[x + x]);
	}
	ii get(int x) {
		return a[get(1, 0, n - 1, x)];
	}
};

int GetBestPosition(int n, int m, int me, int a[], int L[], int R[]) {
	:: n = n;
	:: m = m;
	:: me = me;
	//puts("hereWeGo");
	makeT :: init();
	for(int i = 0; i < m; i++) {
		L[i] = makeT :: get(L[i] + 1).first;
		R[i] = makeT :: get(R[i] + 1).second;
		makeT :: up(L[i], R[i]);
		//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);
		curTime++;
		//printf("L = %d R = %d res = %d\n", L[i], R[i], res);
	}
	solve(1, 0, n - 1);
	assert(best != -1);
	return best;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12988 KB Output is correct
2 Correct 17 ms 13660 KB Output is correct
3 Correct 2 ms 12988 KB Output is correct
4 Correct 14 ms 13516 KB Output is correct
5 Correct 18 ms 13516 KB Output is correct
6 Correct 6 ms 13120 KB Output is correct
7 Correct 20 ms 13516 KB Output is correct
8 Correct 19 ms 13516 KB Output is correct
9 Correct 0 ms 12988 KB Output is correct
10 Correct 13 ms 13252 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 15016 KB Output is correct
2 Correct 574 ms 30456 KB Output is correct
3 Correct 35 ms 13644 KB Output is correct
4 Correct 491 ms 27888 KB Output is correct
5 Correct 501 ms 29144 KB Output is correct
6 Correct 175 ms 17036 KB Output is correct
7 Correct 505 ms 28912 KB Output is correct
8 Correct 543 ms 29240 KB Output is correct
9 Correct 13 ms 13380 KB Output is correct
10 Correct 35 ms 14040 KB Output is correct