#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
#define for1(i,n) for(int i=1;i<=(int)n;i++)
#define for0(i,n) for(int i=0;i<=(int)n;i++)
#define forn(i,n) for(int i=n;i>=1;i--)
#define fo(i,x,y) for(int i=x;i<=(int)y;i++)
#define fr(i,x,y) for(int i=x;i>=(int)y;i--)
#define pb push_back
#define mp make_pair
#define LL long long
const LL Mod=1000*1000*1000+7;
int N;
int K[100002];
int gum[4*100002];
int color[4*100002];
int push(int v,int l,int r)
{
if(color[v]!=-1)
{
color[2*v]=color[v];
color[2*v+1]=color[v];
color[v]=-1;
int m=(l+r)/2;
gum[2*v]=color[2*v]*(m-l+1);
gum[2*v+1]=color[2*v+1]*(r-m);
}
}
void update(int left,int right,int l,int r,int v,int val)
{
if(l>r)
return;
if(left==l && right==r)
{
gum[v]=(right-left+1)*(val);
color[v]=val;
}
else
{
int m=(left+right)/2;
push(v,left,right);
update(left,m,l,min(r,m),2*v,val);
update(m+1,right,max(l,m+1),r,2*v+1,val);
gum[v]=(gum[2*v]+gum[2*v+1]);
}
}
int get(int left,int right,int l,int r,int v)
{
if(l>r)
return 0;
if(left==l && right==r)
return gum[v];
int m=(left+right)/2;
push(v,left,right);
int A=get(left,m,l,min(r,m),2*v);
int B=get(m+1,right,max(l,m+1),r,2*v+1);
return (A+B);
}
int bin_1(int T)
{
int l=0;
int r=(N-1);
while(1)
{
if(l==r)
return l;
int m=(l+r)/2;
if(get(0,N-1,0,m,1)>=T)
r=m;
else
l=(m+1);
}
}
int bin_2(int T)
{
int l=0;
int r=(N-1);
while(1)
{
if(l==r)
return l;
int m=(l+r+1)/2;
if(get(0,N-1,0,m,1)>T)
r=m-1;
else
l=m;
}
}
vector<vector<int> > G(100002);
int leftNod[100002];
int rightNod[100002];
int pos[100002];
int up[100002][25];
int tin[100002];
int tout[100002];
int height[100002];
int timer=0;
bool upper(int a,int b)
{
if(tin[a]<=tin[b] && tout[a]>=tout[b])
return 1;
return 0;
}
int lca(int a,int b)
{
if(upper(a,b)) return a;
if(upper(b,a)) return b;
for(int i=22;i>=0;i--)
{
if(up[a][i]!=-1 && !upper(up[a][i],b))
{
//cout<<a<<" "<<i<<endl;
a=up[a][i];
}
}
return up[a][0];
}
void dfs(int v,int p)
{
if(p!=-1)
height[v]=height[p]+1;
//cout<<v<<" "<<height[v]<<endl;
tin[v]=++timer;
up[v][0]=p;
for1(i,22)
{
if(up[v][i-1]!=-1)
up[v][i]=up[up[v][i-1]][i-1];
else
up[v][i]=-1;
}
for0(i,G[v].size()-1)
{
int to=G[v][i];
if(to!=p)
dfs(to,v);
}
tout[v]=++timer;
}
int mec_dzax[100002];
int mec_aj[100002];
int GetBestPosition(int N_0, int C, int R, int *K_0, int *S, int *E) {
N=N_0;
update(0,N-1,0,N-1,1,1);
for0(i,N-2)
K[i]=K_0[i];
vector<vector<int> > begi(100002);
vector<vector<int> > endi(100002);
//cout<<endl;
for0(i,C-1)
{
int posL=S[i];
int posR=E[i];
int pos_1=bin_1(posL+1);
int pos_2=bin_2(posR+1);
update(0,N-1,pos_1+1,pos_2,1,0);
//cout<<i<<" "<<pos_1<<" "<<pos_2<<endl;
begi[pos_1].push_back(i);
endi[pos_2].push_back(i);
}
//cout<<endl;
//cout<<endl;
stack<int> mystack;
for0(i,N-1)
{
fr(j,begi[i].size()-1,0)
{
int to=begi[i][j];
if(!mystack.empty())
{
int TOP=mystack.top();
G[TOP].push_back(to);
}
mystack.push(to);
}
int TOP=mystack.top();
pos[i]=TOP;
for0(j,endi[i].size()-1)
mystack.pop();
}
dfs(C-1,-1);
/*for0(i,N-1)
{
cout<<i<<" "<<pos[i]<<endl;
}*/
mec_dzax[0]=-1;
mec_aj[N-1]=-1;
for1(i,N-1)
{
if(K[i-1]>R)
mec_dzax[i]=i-1;
else
mec_dzax[i]=mec_dzax[i-1];
}
fr(i,N-2,0)
{
if(K[i]>R)
mec_aj[i]=i;
else
mec_aj[i]=mec_aj[i+1];
}
//int ANS=0;
vector<pair<int,int> > ANS;
for0(i,N-1)
{
//cout<<i<<" "<<pos[i]<<" "<<height[pos[i]]<<endl;
int A=(C-1);
int B=(C-1);
if(mec_dzax[i]==-1 && mec_aj[i]==-1)
{
ANS.pb({height[pos[i]]+1,-i});
continue;
}
if(mec_dzax[i]!=-1)
{
A=pos[mec_dzax[i]];
}
if(mec_aj[i]!=-1)
{
B=pos[mec_aj[i]+1];
}
A=lca(pos[i],A);
B=lca(pos[i],B);
int H=height[pos[i]];
/*if(i==6)
{
cout<<lca(3,5)<<endl;
//cout<<pos[i]<<"dddd"<<endl;
cout<<A1<<" rrr "<<B<<endl;
cout<<mec_dzax[i]<<" ddd "<<mec_aj[i]<<endl;
//cout<<H<<"ccc"<<endl;
}*/
ANS.pb({H-max(height[A],height[B]),-i});
}
//cout<<endl;
sort(ANS.begin(),ANS.end());
return (-ANS[ANS.size()-1].second);
}
/*
5 3 3
1
0
2
4
1 3
0 1
0 1
*/
/*
10 7 3
9 8 7 6 4 5 2 1 0
0 1
1 2
0 1
1 2
0 1
1 4
0 1
*/
Compilation message
tournament.cpp: In function 'int push(int, int, int)':
tournament.cpp:38:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
7416 KB |
Output is correct |
| 2 |
Correct |
10 ms |
7564 KB |
Output is correct |
| 3 |
Correct |
10 ms |
7652 KB |
Output is correct |
| 4 |
Correct |
11 ms |
7816 KB |
Output is correct |
| 5 |
Correct |
9 ms |
7816 KB |
Output is correct |
| 6 |
Correct |
11 ms |
7968 KB |
Output is correct |
| 7 |
Correct |
10 ms |
7968 KB |
Output is correct |
| 8 |
Correct |
12 ms |
7968 KB |
Output is correct |
| 9 |
Correct |
10 ms |
7968 KB |
Output is correct |
| 10 |
Correct |
12 ms |
7968 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
7980 KB |
Output is correct |
| 2 |
Correct |
33 ms |
9320 KB |
Output is correct |
| 3 |
Correct |
13 ms |
9320 KB |
Output is correct |
| 4 |
Correct |
27 ms |
9320 KB |
Output is correct |
| 5 |
Correct |
32 ms |
9332 KB |
Output is correct |
| 6 |
Correct |
27 ms |
9332 KB |
Output is correct |
| 7 |
Correct |
34 ms |
9572 KB |
Output is correct |
| 8 |
Correct |
29 ms |
9572 KB |
Output is correct |
| 9 |
Correct |
10 ms |
9572 KB |
Output is correct |
| 10 |
Correct |
35 ms |
9572 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
232 ms |
17180 KB |
Output is correct |
| 2 |
Correct |
586 ms |
37800 KB |
Output is correct |
| 3 |
Correct |
93 ms |
37800 KB |
Output is correct |
| 4 |
Correct |
652 ms |
37800 KB |
Output is correct |
| 5 |
Correct |
511 ms |
39228 KB |
Output is correct |
| 6 |
Correct |
494 ms |
39228 KB |
Output is correct |
| 7 |
Correct |
646 ms |
42532 KB |
Output is correct |
| 8 |
Correct |
623 ms |
44452 KB |
Output is correct |
| 9 |
Correct |
37 ms |
44452 KB |
Output is correct |
| 10 |
Correct |
83 ms |
44452 KB |
Output is correct |
