#include <iostream>
#include <array>
#include <vector>
#define ll long long
using namespace std;
ll n, x, y, p = -1, f, st[400000], lazy[400000], bit[100001];
vector <array<ll, 2>> V, Q;
array<ll, 2> A[100000];
vector <ll> U;
void add(ll u, ll v) {
while (u <= n) {
bit[u] += v;
u += u & -u;
}
}
ll get(ll u) {
ll res = 0;
while (u) {
res += bit[u];
u -= u & -u;
}
return res;
}
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);
}
ll query(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 query(id*2, l, mid, k);
else return max(mid, query(id*2, 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<C; ++i) {
x = query(1, 0, n-1, S[i]);
y = query(1, 0, n-1, E[i]);
if (x != y) update(1, 0, n-1, x+1, y);
V.push_back({x, y});
}
for (int i=0; i<n; ++i) {
if (K[i] > R) {
Q.push_back({p+1, i});
p = i;
}
}
sort(V.begin(), V.end(), [](auto a, auto b) {
return a[0] > b[0];
});
sort(Q.begin(), Q.end(), [](auto a, auto b) {
return a[0] > b[0];
});
int i=0, j=0;
while (i < V.size() && j < Q.size()) {
if (V[i][0] >= Q[j][0]) {
add(V[i][1]+1, 1);
++i;
}
else {
f = max(f, get(Q[j][1]+1));
++j;
}
}
while (j < Q.size()) {
f = max(f, get(Q[j][1]+1));
++j;
}
return f;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:82:3: error: 'sort' was not declared in this scope; did you mean 'qsort'?
82 | sort(V.begin(), V.end(), [](auto a, auto b) {
| ^~~~
| qsort
tournament.cpp:89:12: 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]
89 | while (i < V.size() && j < Q.size()) {
| ~~^~~~~~~~~~
tournament.cpp:89:28: 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]
89 | while (i < V.size() && j < Q.size()) {
| ~~^~~~~~~~~~
tournament.cpp:99:12: 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]
99 | while (j < Q.size()) {
| ~~^~~~~~~~~~
