Submission #945755

#	Time	Username	Problem	Language	Result	Execution time	Memory
945755		siewjh	Jousting tournament (IOI12_tournament)	C++17	100 / 100	91 ms	14168 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int fw[MAXN], nums;
void fupdate(int p, int v){
	while (p <= nums){
		fw[p] += v;
		p += (p & (-p));
	}
}
int fquery(int p){
	int ans = 0;
	while (p){
		ans += fw[p];
		p -= (p & (-p));
	}
	return ans;
}
struct node{
	int s, e, m, val;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, val = 0;
		if (s != e){
			l = new node(s, m);
			r = new node(m + 1, e);
		}
	}
	void update(int p, int v){
		if (s == e){
			val = v; return;
		}
		else if (p <= m) l->update(p, v);
		else r->update(p, v);
		val = max(l->val, r->val);
	}
	int query(int x, int y){
		if (x == s && y == e) return val;
		else if (y <= m) return l->query(x, y);
		else if (x > m) return r->query(x, y);
		else return max(l->query(x, m), r->query(m + 1, y));
	}
};

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	nums = N;
	set<int> spos;
	for (int i = 1; i <= nums; i++){
		fupdate(i, 1);
		spos.insert(i);
	}
	spos.insert(nums + 1);
	vector<pair<int, int>> rcoords(C);
	for (int i = 0; i < C; i++){
		int s = S[i], e = E[i], l = 1, r = nums, rs, re;
		s++; e++;
		while (l <= r){
			int m = (l + r) >> 1;
			if (fquery(m) >= s){
				rs = m;
				r = m - 1;
			}
			else l = m + 1;
		}
		auto it = spos.lower_bound(rs); it++;
		for (int j = s + 1; j <= e; j++, it = spos.erase(it)) fupdate(*it, -1);
		re = (*it) - 1;
		rcoords[i] = {rs, re};
	}
	node *root = new node(1, nums - 1);
	for (int i = 1; i < nums; i++) root->update(i, K[i - 1]);
	vector<int> cumv(nums + 1);
	for (auto &[s, e] : rcoords)
		if (root->query(s, e - 1) < R){
			cumv[s]++; cumv[e + 1]--;
		}
	int ans = -1, ind, curr = 0;
	for (int i = 1; i <= nums; i++){
		curr += cumv[i];
		if (curr > ans){
			ans = curr;
			ind = i;
		}
	}
	return ind - 1;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:85:15: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   85 |  return ind - 1;
      |               ^

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