oj.uz

Submission #284695

# Submission time Handle Problem Language Result Execution time Memory
284695 2020-08-27T22:01:01 Z ChrisT Jousting tournament (IOI12_tournament) C++17
100 / 100
 291 ms 23924 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <typename t>
using pbds = tree<t,null_type,less<t>,rb_tree_tag,tree_order_statistics_node_update>;
const int MN = 2e5 + 5;
int GetBestPosition(int n, int c, int rnk, int *k, int *s, int *e) {
	vector<vector<int>> sp(__lg(n)+1,vector<int>(n));
	for (int i = 1; i < n; i++) sp[0][i] = k[i-1];
	for (int j = 1; j <= __lg(n); j++)
		for (int i = 1; i + (1 << j) - 1 < n; i++)
			sp[j][i] = max(sp[j-1][i],sp[j-1][i+(1<<(j-1))]);
	auto query = [&] (int l, int r) {
		int lg = __lg(r-l+1);
		int ret = max(sp[lg][l],sp[lg][r-(1<<lg)+1]);
		return ret;
	};
	vector<vector<int>> st(n+1),ed(n+1); pbds<int> l,r;
	for (int i = 1; i <= n; i++) l.insert(i), r.insert(i);
	for (int i = 0; i < c; i++) {
		int sz = e[i] - s[i] + 1;
		int lb = *l.find_by_order(s[i]), rb = *r.find_by_order(e[i]);
		for (int j = 1; j < sz; j++) l.erase(l.find_by_order(s[i] + 1)), r.erase(r.find_by_order(e[i] - j));
		st[lb].emplace_back(rb); ed[rb].emplace_back(lb);
	}
	int cur = 0, best = -1, ret = -1;
	for (int i = 1; i <= n; i++) {
		for (int j : st[i]) if (query(i,j-1) < rnk) ++cur;
		if (cur > best) {
			best = cur;
			ret = i-1;
		}
		for (int j : ed[i]) if (query(j,i-1) < rnk) --cur; 
	}
	return ret;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 11696 KB Output is correct
2 Correct 237 ms 23924 KB Output is correct
3 Correct 192 ms 22256 KB Output is correct
4 Correct 231 ms 23920 KB Output is correct
5 Correct 231 ms 23036 KB Output is correct
6 Correct 291 ms 23280 KB Output is correct
7 Correct 241 ms 23920 KB Output is correct
8 Correct 233 ms 23920 KB Output is correct
9 Correct 198 ms 22000 KB Output is correct
10 Correct 196 ms 22128 KB Output is correct