#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define pb push_back
const int N=100050;
const int M=2*N;
int root;
vector<int> E[M];
int node[N];
set<int> play;
int ls[M],rs[M],sum[M],tsz,rt;
void Set(int &c, int ss, int se, int qi, int val)
{
if(!c) c=++tsz;
sum[c]+=val;
if(ss==se) return;
int mid=ss+se>>1;
if(qi<=mid) Set(ls[c],ss,mid,qi,val);
else Set(rs[c],mid+1,se,qi,val);
}
int Get(int c, int ss, int se, int k)
{
if(ss==se) return ss;
int mid=ss+se>>1;
if(sum[ls[c]]>=k) return Get(ls[c],ss,mid,k);
else return Get(rs[c],mid+1,se,k-sum[ls[c]]);
}
int csz[M],head[M],dep[M],sz[M],par[M][18];
void DFS(int u, int p)
{
par[u][0]=p;
dep[u]=dep[p]+1;
sz[u]=1;
int i;
for(i=1;i<18;i++) par[u][i]=par[par[u][i-1]][i-1];
for(i=0;i<E[u].size();i++) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
}
void HLD(int u)
{
csz[head[u]]++;
int i,HC=0;
for(i=0;i<E[u].size();i++) if(sz[E[u][i]]>sz[HC]) HC=E[u][i];
for(i=0;i<E[u].size();i++)
{
int v=E[u][i];
if(v==HC) head[v]=head[u];
else head[v]=v;
HLD(v);
}
}
vector<int> bit[M];
void Add(int j, int i, int f){ for(;i;i-=i&-i) bit[j][i]+=f;}
int Get(int j, int i){ int ret=0;for(;i<bit[j].size();i+=i&-i) ret+=bit[j][i];return ret;}
void Set(int u, int f)
{
while(u)
{
int id=dep[u]-dep[head[u]]+1;
Add(head[u],id,f);
u=par[head[u]][0];
}
}
int Get(int u){ return Get(head[u],dep[u]-dep[head[u]]+1);}
int GetKth(int u, int k){ for(int i=0;i<18;i++) if((k>>i)&1) u=par[u][i];return u;}
int push[N];
int GetBestPosition(int n, int m, int rank, int *a, int *s, int *e)
{
int i,j;
root=n;
for(i=0;i<n;i++) node[i]=i+1,play.insert(i),Set(rt,0,n-1,i,1);
for(j=0;j<m;j++)
{
int l=Get(rt,0,n-1,s[j]+1);
int r=Get(rt,0,n-1,e[j]+1);
//printf("%i %i\n",l,r);
root++;
set<int>::iterator it;
bool fir=1;
for(it=play.lower_bound(l);it!=play.upper_bound(r);it++)
{
E[root].pb(node[*it]);
//printf("%i -> %i\n",root,node[*it]);
if(!fir) Set(rt,0,n-1,*it,-1);
fir=0;
}
node[*play.lower_bound(l)]=root;
play.erase(play.upper_bound(l),play.upper_bound(r));
}
//printf(":D\n");
DFS(root,0);
head[root]=root;
HLD(root);
for(i=1;i<=root;i++) bit[i].resize(csz[i]+1);
for(i=2;i<=n;i++)
{
if(rank<a[i-2]) Set(i,1),push[i]=1;
}
int sol=-1,ans=-1;
for(i=1;i<=n;i++)
{
int top=dep[i]-1,bot=0,mid,ok=0;
while(top>=bot)
{
mid=top+bot>>1;
if(!Get(GetKth(i,mid))) ok=mid,bot=mid+1;
else top=mid-1;
}
if(ans<ok) ans=ok,sol=i-1;
if(push[i+1])
{
Set(i+1,-1);
Set(i,1);
}
}
return sol;
}
//--------------------//
/*
int A[N],L[N],R[N];
int main()
{
int n,m,rank,i;
scanf("%i %i %i",&n,&m,&rank);
for(i=0;i<n-1;i++) scanf("%i",&A[i]);
for(i=0;i<m;i++) scanf("%i %i",&L[i],&R[i]);
printf("%i\n",GetBestPosition(n,m,rank,A,L,R));
return 0;
}
*/
//--------------------//
Compilation message
tournament.cpp: In function 'void Set(int&, int, int, int, int)':
tournament.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
tournament.cpp: In function 'int Get(int, int, int, int)':
tournament.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=ss+se>>1;
~~^~~
tournament.cpp: In function 'void DFS(int, int)':
tournament.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<E[u].size();i++) DFS(E[u][i],u),sz[u]+=sz[E[u][i]];
~^~~~~~~~~~~~
tournament.cpp: In function 'void HLD(int)':
tournament.cpp:44:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<E[u].size();i++) if(sz[E[u][i]]>sz[HC]) HC=E[u][i];
~^~~~~~~~~~~~
tournament.cpp:45:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<E[u].size();i++)
~^~~~~~~~~~~~
tournament.cpp: In function 'int Get(int, int)':
tournament.cpp:55:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
int Get(int j, int i){ int ret=0;for(;i<bit[j].size();i+=i&-i) ret+=bit[j][i];return ret;}
~^~~~~~~~~~~~~~
tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:106:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
mid=top+bot>>1;
~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
9720 KB |
Output is correct |
| 2 |
Correct |
11 ms |
9960 KB |
Output is correct |
| 3 |
Correct |
12 ms |
10000 KB |
Output is correct |
| 4 |
Correct |
13 ms |
10140 KB |
Output is correct |
| 5 |
Correct |
12 ms |
10140 KB |
Output is correct |
| 6 |
Correct |
14 ms |
10212 KB |
Output is correct |
| 7 |
Correct |
12 ms |
10344 KB |
Output is correct |
| 8 |
Correct |
14 ms |
10352 KB |
Output is correct |
| 9 |
Correct |
15 ms |
10420 KB |
Output is correct |
| 10 |
Correct |
13 ms |
10420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
13 ms |
10620 KB |
Output is correct |
| 2 |
Correct |
28 ms |
12200 KB |
Output is correct |
| 3 |
Correct |
18 ms |
12200 KB |
Output is correct |
| 4 |
Correct |
25 ms |
12312 KB |
Output is correct |
| 5 |
Correct |
25 ms |
12312 KB |
Output is correct |
| 6 |
Correct |
25 ms |
12312 KB |
Output is correct |
| 7 |
Correct |
26 ms |
12504 KB |
Output is correct |
| 8 |
Correct |
28 ms |
12552 KB |
Output is correct |
| 9 |
Correct |
18 ms |
12552 KB |
Output is correct |
| 10 |
Correct |
24 ms |
12568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
170 ms |
23796 KB |
Output is correct |
| 2 |
Correct |
391 ms |
47216 KB |
Output is correct |
| 3 |
Correct |
140 ms |
47216 KB |
Output is correct |
| 4 |
Correct |
387 ms |
47216 KB |
Output is correct |
| 5 |
Correct |
363 ms |
48392 KB |
Output is correct |
| 6 |
Correct |
369 ms |
48392 KB |
Output is correct |
| 7 |
Correct |
400 ms |
52116 KB |
Output is correct |
| 8 |
Correct |
343 ms |
54020 KB |
Output is correct |
| 9 |
Correct |
136 ms |
54020 KB |
Output is correct |
| 10 |
Correct |
196 ms |
54020 KB |
Output is correct |
