oj.uz

Submission #945755

# Submission time Handle Problem Language Result Execution time Memory
945755 2024-03-14T07:23:10 Z siewjh Jousting tournament (IOI12_tournament) C++17
100 / 100
 91 ms 14168 KB 
#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

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.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 968 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 5 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 3 ms 1044 KB Output is correct
8 Correct 3 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 5 ms 1112 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 6244 KB Output is correct
2 Correct 81 ms 14148 KB Output is correct
3 Correct 41 ms 11600 KB Output is correct
4 Correct 91 ms 14168 KB Output is correct
5 Correct 88 ms 13488 KB Output is correct
6 Correct 91 ms 13008 KB Output is correct
7 Correct 80 ms 13920 KB Output is correct
8 Correct 87 ms 14020 KB Output is correct
9 Correct 39 ms 11332 KB Output is correct
10 Correct 49 ms 11656 KB Output is correct