#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ALL(i) i.begin(), i.end()
#define SZ(i) int(i.size())
#define X first
#define Y second
#define eb emplace_back
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream& __printRng (ostream& os, IT bg, IT ed) {
for (IT it=bg;it!=ed;it++) {
if (it == bg) os << "{" << *it;
else os << "," << *it;
}
return os << "}";
}
template<typename T> ostream& operator << (ostream& os, const vector<T> &vec) {
return __printRng(os, ALL(vec));
}
template<typename T, typename S> ostream& operator << (ostream& os, const pair<T,S> &pa) {
return os << "{" << pa.X << "," << pa.Y << "}";
}
#else
#define debug(...)
#endif
typedef pair<int,int> pii;
const int MAXN = 100005;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rk;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> fid;
int L[MAXN], R[MAXN], n;
vector<int> in[MAXN], out[MAXN];
int seg[MAXN*2], sn;
void build () {
for (int i=sn-1; i>0; i--) {
seg[i] = max(seg[i<<1], seg[i<<1|1]);
}
}
int qry (int l, int r) {
int ret = 0;
for (l+=sn, r+=sn; l<r; l>>=1, r>>=1) {
if (l&1) ret = max(ret, seg[l++]);
if (r&1) ret = max(ret, seg[--r]);
}
return ret;
}
int GetBestPosition(int N, int C, int Z, int *K, int *S, int *E) {
int r, c;
n = N;
sn = n-1;
c = C;
r = Z;
vector<pii> fg;
for (int i=0; i<n; i++) {
rk.insert(i);
L[i] = R[i] = i;
}
for (int i=0; i<c; i++) {
auto ptr = rk.find_by_order(S[i]);
int len = E[i] - S[i] + 1;
vector<int> rmv;
int lid = *ptr;
int cl = L[lid];
int cr = R[lid];
for (int j=0; j<len-1; j++) {
ptr++;
rmv.emplace_back(*ptr);
}
for (int v : rmv) {
cl = min(cl, L[v]);
cr = max(cr, R[v]);
rk.erase(v);
}
L[lid] = cl;
R[lid] = cr;
in[cl].emplace_back(i);
out[cr].emplace_back(i);
fg.emplace_back(cl, cr);
}
debug(fg);
assert(rk.size() == 1);
for (int i=0; i<n-1; i++) {
seg[i+sn] = K[i];
}
build();
pii ans = {-1, 0};
for (int i=0; i<n; i++) {
for (int id : in[i]) fid.insert(id);
debug(in[i], out[i]);
int sl = -1, sr = SZ(fid);
#ifdef tmd
__printRng(cerr, ALL(fid));
#endif
while (sl < sr - 1) {
int sm = (sl + sr) >> 1;
pii rng = fg[*fid.find_by_order(sm)];
rng.Y--;
int rn = qry(rng.X, rng.Y + 1);
debug(i, rng, rn, sm);
if (qry(rng.X, rng.Y + 1) < r) {
sl = sm;
} else {
sr = sm;
}
}
// int sr = 0;
// for (int id : fid) {
// pii rng = fg[id];
// rng.Y--;
// if (qry(rng.X, rng.Y + 1) < r) sr++;
// }
#ifdef tmd
vector<int> cur;
int val = 0;
for (int j=0,ptr=0; j<n; j++) {
if (j == i) cur.eb(r);
else cur.eb(K[ptr++]);
}
for (int j=0; j<c; j++) {
vector<int> nw;
for (int k=0; k<S[j]; k++) {
nw.eb(cur[k]);
}
int mx = 0;
for (int k=S[j]; k<=E[j]; k++) {
mx = max(mx, cur[k]);
}
nw.eb(mx);
for (int k=E[j]+1;k<SZ(cur);k++) {
nw.eb(cur[k]);
}
cur = nw;
val += mx == r;
}
if (val != sr) {
debug(i, val, sr);
cout << "FATAL ERROR" << endl;
debug(n, c, r);
for (int j=0; j<n-1; j++) {
cout << K[j] << " ";
}
cout << endl;
for (int j=0; j<c; j++) cout << S[j] << " " << E[j] << endl;
return -1;
}
#endif
ans = max(ans, {sr, -i});
for (int id : out[i]) fid.erase(id);
}
debug(ans);
return -ans.Y;
}
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:116:17: warning: unused variable 'rn' [-Wunused-variable]
116 | int rn = qry(rng.X, rng.Y + 1);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 9 |
Correct |
4 ms |
4992 KB |
Output is correct |
| 10 |
Correct |
4 ms |
5120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 2 |
Correct |
16 ms |
5632 KB |
Output is correct |
| 3 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 4 |
Correct |
14 ms |
5504 KB |
Output is correct |
| 5 |
Correct |
14 ms |
5504 KB |
Output is correct |
| 6 |
Correct |
10 ms |
5504 KB |
Output is correct |
| 7 |
Correct |
16 ms |
5504 KB |
Output is correct |
| 8 |
Correct |
16 ms |
5504 KB |
Output is correct |
| 9 |
Correct |
7 ms |
5376 KB |
Output is correct |
| 10 |
Correct |
12 ms |
5632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
9460 KB |
Output is correct |
| 2 |
Correct |
448 ms |
16364 KB |
Output is correct |
| 3 |
Correct |
122 ms |
12500 KB |
Output is correct |
| 4 |
Correct |
384 ms |
13804 KB |
Output is correct |
| 5 |
Correct |
402 ms |
14384 KB |
Output is correct |
| 6 |
Correct |
209 ms |
13424 KB |
Output is correct |
| 7 |
Correct |
443 ms |
14572 KB |
Output is correct |
| 8 |
Correct |
436 ms |
14572 KB |
Output is correct |
| 9 |
Correct |
111 ms |
12200 KB |
Output is correct |
| 10 |
Correct |
119 ms |
12152 KB |
Output is correct |
