#include <bits/stdc++.h>
using namespace std;
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define Add(x,y) x=(x+y)%mod
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=2e5+99;
int n,m,Rank,ans,max_ans,id[N],a[N],s[N],t[N],vl[N],vr[N],fa[N],h[N],seg[N],NN,C,R,K[N],S[N],E[N];
vector<int> g[N];
int Fen[N];
void update(int x,int val) { x++; while(x<N) { Fen[x]+=val; x+=(x&-x); } }
int query(int x) { x++; int res=0; while(x>0) { res+=Fen[x]; x-=(x&-x); } return res; }
void build(){
f(i,0,n){
seg[i+n]=a[i];
}
f_(i,n-1,1){
seg[i]=max(seg[i*2+0],seg[i*2+1]);
}
}
int Get(int l,int r){
int ans=0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l&1) maxm(ans,seg[l++]);
if (r&1) maxm(ans,seg[--r]);
}
return ans;
}
int find(int x){
int l=-1,r=n;
while(l+1<r){
int mid=(l+r)/2;
if(query(mid)<=x) l=mid;
else r=mid;
}
return r;
}
void dfs(int x){
fa[x]=x;
vl[x]=N,vr[x]=0;
f(i,0,g[x].size()){
h[g[x][i]]=h[x]+1;
dfs(g[x][i]);
minm(vl[x],vl[g[x][i]]);
maxm(vr[x],vr[g[x][i]]);
if(h[fa[g[x][i]]]>h[fa[x]]){
fa[x]=fa[g[x][i]];
}
}
if(x<n){
vl[x]=x;
vr[x]=x;
}
if(Get(vl[x],vr[x])<Rank && h[fa[x]]-h[x]+1>max_ans){
ans=fa[x];
max_ans=h[fa[x]]-h[x]+1;
}
}
void make_tree(){
f(i,0,n){
id[i]=i;
update(i,1);
}
f(i,0,m){
vector<int> v;
int x,len=t[i]-s[i]+1;
f(T,0,len){
x=find(s[i]);
update(x,-1);
g[n+i].pb(id[x]);
}
id[x]=n+i;
update(x,1);
}
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E){
n=N,m=C,Rank=R;
f(i,0,n-1) a[i]=K[i];
f(i,0,C){
s[i]=S[i];
t[i]=E[i];
}
build();
make_tree();
dfs(n+m-1);
return ans;
}
Compilation message
tournament.cpp: In function 'void dfs(int)':
tournament.cpp:7:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
57 | f(i,0,g[x].size()){
| ~~~~~~~~~~~~~~~
tournament.cpp:57:2: note: in expansion of macro 'f'
57 | f(i,0,g[x].size()){
| ^
tournament.cpp: In function 'void make_tree()':
tournament.cpp:26:31: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
26 | void update(int x,int val) { x++; while(x<N) { Fen[x]+=val; x+=(x&-x); } }
| ~^~
tournament.cpp:82:7: note: 'x' was declared here
82 | int x,len=t[i]-s[i]+1;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
5068 KB |
Output is correct |
2 |
Correct |
3 ms |
5068 KB |
Output is correct |
3 |
Correct |
2 ms |
5068 KB |
Output is correct |
4 |
Correct |
3 ms |
5068 KB |
Output is correct |
5 |
Correct |
3 ms |
5020 KB |
Output is correct |
6 |
Correct |
3 ms |
5068 KB |
Output is correct |
7 |
Correct |
2 ms |
5068 KB |
Output is correct |
8 |
Correct |
3 ms |
5068 KB |
Output is correct |
9 |
Correct |
2 ms |
5068 KB |
Output is correct |
10 |
Correct |
3 ms |
5068 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
5068 KB |
Output is correct |
2 |
Correct |
8 ms |
5964 KB |
Output is correct |
3 |
Correct |
4 ms |
5324 KB |
Output is correct |
4 |
Correct |
6 ms |
5664 KB |
Output is correct |
5 |
Correct |
8 ms |
5740 KB |
Output is correct |
6 |
Correct |
6 ms |
5452 KB |
Output is correct |
7 |
Correct |
6 ms |
5836 KB |
Output is correct |
8 |
Correct |
8 ms |
5708 KB |
Output is correct |
9 |
Correct |
3 ms |
5324 KB |
Output is correct |
10 |
Correct |
7 ms |
5580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
8912 KB |
Output is correct |
2 |
Correct |
90 ms |
23376 KB |
Output is correct |
3 |
Correct |
37 ms |
9728 KB |
Output is correct |
4 |
Correct |
92 ms |
18200 KB |
Output is correct |
5 |
Correct |
90 ms |
19788 KB |
Output is correct |
6 |
Correct |
85 ms |
12884 KB |
Output is correct |
7 |
Correct |
90 ms |
19936 KB |
Output is correct |
8 |
Correct |
89 ms |
19924 KB |
Output is correct |
9 |
Correct |
32 ms |
9364 KB |
Output is correct |
10 |
Correct |
40 ms |
9724 KB |
Output is correct |