#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;
ll n, x, y, p = -1, s, f, tmp, id = 0, st[400000], lazy[400000];
vector <array<ll, 2>> V;
vector <ll> U;
array<ll, 2> A[100000];
void push(ll id) {
if (lazy[id]) {
st[id*2] = st[id*2+1] = 0;
lazy[id*2] = lazy[id*2+1] = 1;
lazy[id] = 0;
}
}
void update(ll id, ll l, ll r, ll ql, ll qr) {
if (qr < l || r < ql) return;
else if (ql <= l && r <= qr) {
st[id] = 0;
lazy[id] = 1;
return;
}
push(id);
ll mid = (l+r)/2;
update(id*2, l, mid, ql, qr);
update(id*2+1, mid+1, r, ql, qr);
st[id] = st[id*2] + st[id*2+1];
}
ll queryL(ll id, ll l, ll r, ll k) {
if (l == r) return l;
push(id);
ll mid = (l+r)/2;
if (st[id*2] >= k) return queryL(id*2, l, mid, k);
else return queryL(id*2+1, mid+1, r, k-st[id*2]);
}
ll queryR(ll id, ll l, ll r, ll k) {
if (l == r) {
if (st[id] == k) return l;
else return -1e18;
}
push(id);
ll mid = (l+r)/2;
if (st[id*2] > k) return queryR(id*2, l, mid, k);
else return max(mid, queryR(id*2+1, mid+1, r, k-st[id*2]));
}
void build(ll id, ll l, ll r) {
if (l == r) {
st[id] = 1;
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = st[id*2] + st[id*2+1];
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
n = N;
build(1, 0, n-1);
for (int i=0; i<n-1; ++i) {
if (K[i] > R) {
U.push_back(i);
}
}
for (int i=0; i<C; ++i) {
++S[i], ++E[i];
x = queryL(1, 0, n-1, S[i]);
y = queryR(1, 0, n-1, E[i]);
if (x != y) update(1, 0, n-1, x+1, y);
auto it = lower_bound(U.begin(), U.end(), x);
if (it == U.end() || *it+1 > y) {
V.push_back({x, 1});
V.push_back({y+1, -1});
}
}
sort(V.begin(), V.end());
int j=0;
for (int i=0; i<n; ++i) {
while (j < V.size()) {
if (V[j][0] == i) s += V[j++][1];
else break;
}
if (s > f) {
f = s;
id = i;
}
}
return id;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:84:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | while (j < V.size()) {
| ~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
1 ms |
4440 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
1 ms |
4444 KB |
Output is correct |
5 |
Correct |
1 ms |
4444 KB |
Output is correct |
6 |
Correct |
1 ms |
4444 KB |
Output is correct |
7 |
Correct |
1 ms |
4548 KB |
Output is correct |
8 |
Correct |
1 ms |
4444 KB |
Output is correct |
9 |
Correct |
1 ms |
4444 KB |
Output is correct |
10 |
Correct |
1 ms |
4444 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
4444 KB |
Output is correct |
2 |
Correct |
3 ms |
4700 KB |
Output is correct |
3 |
Correct |
2 ms |
4444 KB |
Output is correct |
4 |
Correct |
3 ms |
4700 KB |
Output is correct |
5 |
Correct |
3 ms |
4700 KB |
Output is correct |
6 |
Correct |
3 ms |
4700 KB |
Output is correct |
7 |
Correct |
4 ms |
4700 KB |
Output is correct |
8 |
Correct |
3 ms |
4700 KB |
Output is correct |
9 |
Correct |
1 ms |
4556 KB |
Output is correct |
10 |
Correct |
4 ms |
4700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
8660 KB |
Output is correct |
2 |
Correct |
60 ms |
11716 KB |
Output is correct |
3 |
Correct |
13 ms |
8444 KB |
Output is correct |
4 |
Correct |
68 ms |
11332 KB |
Output is correct |
5 |
Correct |
66 ms |
12264 KB |
Output is correct |
6 |
Correct |
53 ms |
10512 KB |
Output is correct |
7 |
Correct |
63 ms |
11084 KB |
Output is correct |
8 |
Correct |
59 ms |
12332 KB |
Output is correct |
9 |
Correct |
9 ms |
6868 KB |
Output is correct |
10 |
Correct |
13 ms |
7892 KB |
Output is correct |