#include <bits/stdc++.h>
/// 500 485 462 A4
using namespace std;
typedef long long int ll;
typedef complex<double> point;
typedef long double ld;
#define pb push_back
#define pii pair < ll , ll >
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
const int MAXN=2e5+100,M=20;
ll fen[MAXN];
ll par[MAXN][M];
void add(ll idx,ll val){
for (;idx<MAXN;idx+= idx & (-idx)){
fen[idx]+=val;
}
}
ll getsum(ll idx){
ll s=0;
for (;idx;idx-= idx & (-idx)){
s+=fen[idx];
}
return s;
}
ll getk(ll k){
ll l=-1,r=MAXN-1;
while(r-l>1){
ll mid=(r+l)/2;
if (getsum(mid)>=k) r=mid;
else l=mid;
}
return r;
}
pii baze[MAXN];
vector <int> g[MAXN];
ll seg[MAXN*4];
void upd(ll nod,ll l,ll r,ll id,ll val){
if (r-l==1){
seg[nod]=val;
return ;
}
ll mid=(r+l)/2;
if (mid>id) upd(nod*2,l,mid,id,val);
else upd(nod*2+1,mid,r,id,val);
seg[nod]=max(seg[nod*2],seg[nod*2+1]);
}
ll get(ll nod,ll l,ll r,ll L,ll R){
if (l>=R || L>=r) return 0;
if (l>=L && r<=R) return seg[nod];
ll mid=(r+l)/2;
return max(get(nod*2+1,mid,r,L,R),get(nod*2,l,mid,L,R));
}
vector <pii> b;
pii baz[MAXN];
ll getpar(ll v,ll h){
for (int i=0;i<M;i++){
if ((h & (1<<i))) v=par[v][i];
}
return v;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
set <int> s;
for (int i=1;i<=N;i++){
s.insert(i);
baze[i]={i,i};
add(i,1);
}
for (int i=0;i<C;i++){
S[i]++;
E[i]++;
ll l=getk(S[i]);
ll r=getk(E[i]);
baze[l].S=baze[r].S;
b.pb({baze[l].F,baze[l].S});
while(true){
auto t=s.upper_bound(l);
if (t==s.end()) break;
if (*t>r) break;
add(*t,-1);
s.erase(t);
}
}
sort(b.begin(),b.end());
// for (auto u : b){
// cout << u.F << " rth " << u.S << endl;
//}
// return 0;
vector <pair <pii,int> > a;
for (int i=1;i<=N;i++){
a.pb({{i,-i},i});
baz[i]={i,i};
}
for (int i=0;i<b.size();i++){
a.pb({{b[i].F,-b[i].S},i+N+1});
baz[i+N+1]=b[i];
}
a.pb({{0,-N*2},0});
sort(a.begin(),a.end());
vector <int> agh;
agh.pb(0);
for (int i=1;i<a.size();i++){
// cout << i << endl;
while(-a[agh.back()].F.S<-a[i].F.S){
agh.pop_back();
}
par[a[i].S][0]=a[agh.back()].S;
// cout << a[i].S << " " << a[i].F.F << " " << a[i].F.S << " " << par[a[i].S][0] << endl;
agh.pb(i);
}
// return 0;
for (int j=1;j<M;j++){
for (int i=0;i<N*2;i++){
par[i][j]=par[par[i][j-1]][j-1];
}
}
for (int i=1;i<N;i++){
upd(1,1,N,i,K[i-1]);
}
ll mx=0,ans=0;
for (int i=1;i<=N;i++){
ll v=i;
ll cnt=0;
for (int i=M-1;i>-1;i--){
ll u=par[v][i];
if (u==0) continue;
ll l=baz[u].F,r=baz[u].S;
ll w=get(1,1,N,l,r);
if (w<R){
//cout << v << " " << u << " " << w << endl;
v=u;
cnt+=(1<<i);
}
}
if (cnt>mx){
ans=i-1;
mx=cnt;
}
}
// cout << mx << endl;
return ans;
}
/*
int main() {
int tmp;
char *inbuf, *outbuf;
inbuf = (char*) malloc(inbuf_len * sizeof(char));
outbuf = (char*) malloc(outbuf_len * sizeof(char));
tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
assert(tmp == 0);
tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
assert(tmp == 0);
int N, C, R;
int *K, *S, *E;
tmp = scanf("%d %d %d", &N, &C, &R);
assert(tmp == 3);
K = (int*) malloc((N-1) * sizeof(int));
S = (int*) malloc(C * sizeof(int));
E = (int*) malloc(C * sizeof(int));
int i;
for (i = 0; i < N-1; i++) {
tmp = scanf("%d", &K[i]);
assert(tmp == 1);
}
for (i = 0; i < C; i++) {
tmp = scanf("%d %d", &S[i], &E[i]);
assert(tmp == 2);
}
printf("%d\n", GetBestPosition(N, C, R, K, S, E));
return 0;
}
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
Compilation message
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:102:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
102 | for (int i=0;i<b.size();i++){
| ~^~~~~~~~~
tournament.cpp:110:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for (int i=1;i<a.size();i++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
5100 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5100 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5376 KB |
Output is correct |
| 7 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 8 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 9 |
Correct |
5 ms |
5356 KB |
Output is correct |
| 10 |
Correct |
5 ms |
5356 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
5612 KB |
Output is correct |
| 2 |
Correct |
21 ms |
7704 KB |
Output is correct |
| 3 |
Correct |
11 ms |
7408 KB |
Output is correct |
| 4 |
Correct |
19 ms |
7720 KB |
Output is correct |
| 5 |
Correct |
19 ms |
7448 KB |
Output is correct |
| 6 |
Correct |
15 ms |
7660 KB |
Output is correct |
| 7 |
Correct |
21 ms |
7704 KB |
Output is correct |
| 8 |
Correct |
23 ms |
7720 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7276 KB |
Output is correct |
| 10 |
Correct |
21 ms |
7720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
152 ms |
29656 KB |
Output is correct |
| 2 |
Correct |
615 ms |
55896 KB |
Output is correct |
| 3 |
Correct |
276 ms |
50284 KB |
Output is correct |
| 4 |
Correct |
552 ms |
56096 KB |
Output is correct |
| 5 |
Correct |
572 ms |
52680 KB |
Output is correct |
| 6 |
Correct |
335 ms |
53712 KB |
Output is correct |
| 7 |
Correct |
594 ms |
55896 KB |
Output is correct |
| 8 |
Correct |
609 ms |
55896 KB |
Output is correct |
| 9 |
Correct |
207 ms |
49900 KB |
Output is correct |
| 10 |
Correct |
231 ms |
50312 KB |
Output is correct |
