#include <bits/stdc++.h>
using namespace std;
int GetBestPosition(int n, int m, int r, int* k, int* s, int* e) {
int sol = 0;
vector<int> bit(n + 2), win(n + 1), link(n + 1), ans(n + 1);
auto update = [&](int pos, int val) {
for (++pos; pos <= n + 1; pos += pos & -pos)
bit[pos] += val;
};
auto query = [&](int val) {
int pos = 0, s = 0;
for (int i = 31 - __builtin_clz(n + 1); ~i; --i)
if (pos + (1 << i) < n + 1 && s + bit[pos + (1 << i)] < val)
pos += 1 << i, s += bit[pos];
return pos;
};
for (int i = 0; i < n; ++i) {
link[i] = i + 1;
win[i + 1] = win[i] + (k[i] > r);
update(i, 1);
}
for (int i = 0; i < m; ++i) {
int l = query(s[i] + 1), r = query(e[i] + 2);
for (int j = link[l], next; j != r; j = next) {
update(j, -1);
next = link[j];
link[j] = r;
}
link[l] = r;
if (!(win[r - 1] - win[l]))
++ans[l], --ans[r - 1];
}
for (int i = 1; i < n; ++i) {
ans[i] += ans[i - 1];
if (ans[i] > ans[sol])
sol = i;
}
return sol;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
304 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
440 KB |
Output is correct |
3 |
Correct |
1 ms |
316 KB |
Output is correct |
4 |
Correct |
2 ms |
440 KB |
Output is correct |
5 |
Correct |
2 ms |
436 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
388 KB |
Output is correct |
8 |
Correct |
2 ms |
436 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
2132 KB |
Output is correct |
2 |
Correct |
48 ms |
4652 KB |
Output is correct |
3 |
Correct |
15 ms |
2900 KB |
Output is correct |
4 |
Correct |
48 ms |
4648 KB |
Output is correct |
5 |
Correct |
44 ms |
4428 KB |
Output is correct |
6 |
Correct |
35 ms |
3916 KB |
Output is correct |
7 |
Correct |
46 ms |
4652 KB |
Output is correct |
8 |
Correct |
48 ms |
4592 KB |
Output is correct |
9 |
Correct |
13 ms |
2796 KB |
Output is correct |
10 |
Correct |
15 ms |
2872 KB |
Output is correct |