Submission #61688

#	Time	Username	Problem	Language	Result	Execution time	Memory
61688		aome	Jousting tournament (IOI12_tournament)	C++17	100 / 100	158 ms	5792 KiB

tournament

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

struct SegmentTree {
	int T[4 * N];

	#define mid ((l + r) >> 1)

	void build(int i, int l, int r) {
		if (l == r) { T[i] = 1; return; }
		build(i << 1, l, mid);
		build(i << 1 | 1, mid + 1, r);
		T[i] = T[i << 1] + T[i << 1 | 1];
	}

	void upd(int i, int l, int r, int p) {
		if (l == r) { T[i] = 0; return; }
		if (mid >= p) upd(i << 1, l, mid, p);
		else upd(i << 1 | 1, mid + 1, r, p);
		T[i] = T[i << 1] + T[i << 1 | 1];
	}

	int get(int i, int l, int r, int k) {
		if (l == r) return l;
		if (T[i << 1] >= k) return get(i << 1, l, mid, k);
		else return get(i << 1 | 1, mid + 1, r, k - T[i << 1]); 
	}

	#undef mid
} IT;

struct Seg {
	int l, r;
	pair<int, int> v;

	bool operator < (const Seg& rhs) const {
		return l > rhs.l;
	}
};

pair<int, int> a[N];
pair<int, int> bit[N];

void upd(int x, pair<int, int> y) {
	for (int i = x; i < N; i += i & -i) bit[i] = max(bit[i], y);
}

pair<int, int> get(int x) {
	pair<int, int> ret = {0, 0};
	for (int i = x; i > 0; i -= i & -i) ret = max(ret, bit[i]);
	return ret;
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E) {
	vector<Seg> seg;
	IT.build(1, 0, n - 1);
	for (int i = 0; i < n; ++i) a[i] = {0, -i};
	for (int i = 0; i < C; ++i) {
		vector<int> vec;
		for (int j = S[i]; j <= E[i]; ++j) {
			vec.push_back(IT.get(1, 0, n - 1, j + 1));
		}
		int l = vec[0];
		for (auto j : vec) a[j].first++;
		for (auto j : vec) {
			a[vec[0]] = max(a[vec[0]], a[j]);
		}
		int r = (E[i] == (IT.T[1] - 1)) ? n - 1 : (IT.get(1, 0, n - 1, E[i] + 2) - 1);
		seg.push_back({l, r, a[vec[0]]});
		for (int j = 1; j < vec.size(); ++j) {
			IT.upd(1, 0, n - 1, vec[j]);
		}
	}
	vector<Seg> seg2;
	for (int i = 0; i < (n - 1); ++i) {
		if (K[i] > R) continue;
		int r = i;
		while (r < (n - 1) && K[r] <= R) r++;
		seg2.push_back({i, r, make_pair(0, 0)});
		i = r;
	}
	sort(seg.begin(), seg.end());
	sort(seg2.begin(), seg2.end());
	// cout << "#seg\n";
	// for (auto i : seg) cout << i.l << ' ' << i.r << ' ' << i.v.first << ' ' << i.v.second << '\n';
	// cout << "#seg2\n";
	// for (auto i : seg2) cout << i.l << ' ' << i.r << '\n';
	int ptr = 0;
	pair<int, int> res = {0, 0};
	for (auto i : seg2) {
		while (ptr < seg.size() && seg[ptr].l >= i.l) {
			upd(seg[ptr].r + 1, seg[ptr].v), ++ptr;
		}
		res = max(res, get(i.r + 1));
	}
	return -res.second;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j < vec.size(); ++j) {
                   ~~^~~~~~~~~~~~
tournament.cpp:94:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr < seg.size() && seg[ptr].l >= i.l) {
          ~~~~^~~~~~~~~~~~

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