Submission #945743

#	Time	Username	Problem	Language	Result	Execution time	Memory
945743		siewjh	Jousting tournament (IOI12_tournament)	C++17	0 / 100	48 ms	12916 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, lazy;
	node *l, *r;
	node (int _s, int _e){
		s = _s, e = _e, m = (s + e) >> 1, val = 0, lazy = 0;
		if (s != e){
			l = new node(s, m);
			r = new node(m + 1, e);
		}
	}
	void push(int v){
		val += v; lazy += v;
	}
	void propo(){
		if (s == e) return;
		if (lazy != 0){
			l->push(lazy); r->push(lazy);
			lazy = 0;
		}
	}
	void update(int x, int y, int v){
		if (s == e){
			push(v); return;
		}
		propo();
		if (y <= m) l->update(x, y, v);
		else if (x > m) r->update(x, y, v);
		else{
			l->update(x, m, v); r->update(m + 1, y, v);
		}
		propo();
		val = max(l->val, r->val);
	}
	int query(int x, int y){
		if (x == s && y == e) return val;
		propo();
		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 qind(){
		if (s == e) return s;
		propo();
		if (l->val >= r->val) return l->qind();
		else return r->qind();
	}
};

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++) fupdate(*it, -1);
		re = (*it) - 1;
		rcoords[i] = {rs, re};
	}
	node *root = new node(1, nums - 1), *root2 = new node(1, nums);
	for (int i = 1; i < nums; i++) root->update(i, i, K[i - 1]);
	for (auto &[s, e] : rcoords)
		if (root->query(s, e - 1) < R)
			root2->update(s, e, 1);
	return root2->qind() - 1;
}

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