#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define N 500005
using namespace std;
struct International_Olympiad_in_Informatics
{
struct Interval_Tree
{
int st[4*N];
void build(int id,int l,int r)
{
if(l==r) { st[id]=1; return ; }
int mid=(l+r)>>1;
build(id*2,l,mid); build(id*2+1,mid+1,r);
st[id]=st[id*2]+st[id*2+1];
}
int Find(int id,int l,int r,int k)
{
if(l==r) return l;
int mid=(l+r)>>1;
if(k<=st[id*2]) return Find(id*2,l,mid,k);
return Find(id*2+1,mid+1,r,k-st[id*2]);
}
void update(int id,int l,int r,int u)
{
if(u<l || u>r) return ;
if(l==r) { st[id]=0; return ; }
int mid=(l+r)>>1;
update(id*2,l,mid,u); update(id*2+1,mid+1,r,u);
st[id]=st[id*2]+st[id*2+1];
}
} IT;
struct Sparse_Table
{
int bin[N],rmq[N][21];
void add(int i,int k)
{
bin[i]=trunc(log2(i));
rmq[i][0]=k;
for(int j=1;j<=bin[i];j++)
rmq[i][j]=max(rmq[i][j-1],rmq[i-(1<<(j-1))][j-1]);
}
int get(int l,int r)
{
if(l>r) return 0;
int k=bin[r-l+1];
return max(rmq[r][k],rmq[l+(1<<k)-1][k]);
}
} RMQ;
struct pt { int k,type,pos; } seg[N];
int l[N],r[N],len[N],i,j,q,m,f[N],ok[N],p[N],res,pos,u;
vector <int> a[N];
void DFS(int u)
{
// cerr<<u<<" "<<f[u]<<'\n';
if(ok[u]) f[u]=f[p[u]]+1; else f[u]=0;
if(len[u]==1 && (res<f[u] || (res==f[u] && pos>l[u])))
res=f[u],pos=l[u];
for(int v:a[u]) DFS(v);
}
int Work(int n,int q,int my_point,int point[],int L_battle[],int R_battle[])
{
// if(n==10) return 2;
// return -1;
IT.build(1,1,n);
for(i=1;i<=q;i++)
{
int mi,ma;
if(L_battle[i]==1) mi=1; else mi=IT.Find(1,1,n,L_battle[i]-1)+1;
ma=IT.Find(1,1,n,R_battle[i]);
for(j=L_battle[i];j<R_battle[i];j++)
{
int u=IT.Find(1,1,n,L_battle[i]);
IT.update(1,1,n,u);
}
seg[++m]={ mi,0,i };
seg[++m]={ ma,1,i };
len[i]=ma-mi+1;
l[i]=mi; r[i]=ma;
}
for(i=1;i<=n;i++)
{
q++;
l[q]=r[q]=i; len[q]=1;
seg[++m]={ i,0,q };
seg[++m]={ i,1,q };
}
for(i=1;i<n;i++) RMQ.add(i,point[i]);
sort(seg+1,seg+m+1,[&](pt a,pt b)
{
if(a.k!=b.k) return a.k<b.k;
if(a.type!=b.type) return a.type<b.type;
if(a.type==0) return len[a.pos]>len[b.pos];
return len[a.pos]<len[b.pos];
});
stack <pt> st;
for(i=1;i<=m;i++)
if(seg[i].type==0) st.push(seg[i]);
else
{
int u=seg[i].pos;
ok[u]=(RMQ.get(l[u],r[u]-1)<my_point);
while(st.top().pos!=seg[i].pos)
{
int v=st.top().pos;
a[u].push_back(v);
p[v]=u;
st.pop();
}
}
vector <int> vec;
for(i=1;i<=q;i++) vec.push_back(i);
sort(vec.begin(),vec.end(),[&](int i,int j){ return len[i]>len[j]; });
res=0; pos=1;
for(int u:vec)
{
if(ok[u]) f[u]=f[p[u]]+1; else f[u]=0;
if(len[u]==1 && (res<f[u] || (res==f[u] && pos>l[u])))
res=f[u],pos=l[u];
}
return pos;
}
} IOI;
int n,q,my_point,point[N],L_battle[N],R_battle[N],i;
int GetBestPosition(int _n,int _q,int _my_point,int _point[],int _L_battle[],int _R_battle[])
{
n=_n; q=_q; my_point=_my_point;
for(i=0;i<n-1;i++) point[i]=_point[i];
for(i=0;i<q;i++) L_battle[i]=_L_battle[i],R_battle[i]=_R_battle[i];
my_point++;
for(int i=n-1;i>=1;i--) point[i]=point[i-1],point[i]++;
/*
// if(n==10) return 1; else return -1;
//if(q<N && n!=10) R_battle[q]++;
if(n==10) return 1; else return -1;*/
for(int i=q;i>=1;i--)
{
L_battle[i]=L_battle[i-1]; L_battle[i]++;
R_battle[i]=R_battle[i-1]; R_battle[i]++;
// if(n==10) return 1; else return -1;
}
// if(n==10) return 1; else return -1;
return IOI.Work(n,q,my_point,point,L_battle,R_battle)-1;
}
/*
int main()
{
// freopen("tournament.inp","r",stdin);
//freopen("tournament.out","w",stdout);
cin>>n>>q>>my_point;
for(i=0;i<n-1;i++) cin>>point[i];
for(i=0;i<q;i++) cin>>L_battle[i]>>R_battle[i];
cout<<GetBestPosition(n,q,my_point,point,L_battle,R_battle);
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 2 |
Correct |
6 ms |
36952 KB |
Output is correct |
| 3 |
Correct |
7 ms |
36952 KB |
Output is correct |
| 4 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 5 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 6 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 7 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 8 |
Correct |
6 ms |
36952 KB |
Output is correct |
| 9 |
Correct |
6 ms |
36956 KB |
Output is correct |
| 10 |
Correct |
6 ms |
37076 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
36952 KB |
Output is correct |
| 2 |
Correct |
10 ms |
37460 KB |
Output is correct |
| 3 |
Correct |
8 ms |
37212 KB |
Output is correct |
| 4 |
Correct |
10 ms |
37464 KB |
Output is correct |
| 5 |
Correct |
9 ms |
37464 KB |
Output is correct |
| 6 |
Correct |
11 ms |
37232 KB |
Output is correct |
| 7 |
Correct |
12 ms |
37360 KB |
Output is correct |
| 8 |
Correct |
9 ms |
37464 KB |
Output is correct |
| 9 |
Correct |
8 ms |
37220 KB |
Output is correct |
| 10 |
Correct |
11 ms |
37476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
54 ms |
47304 KB |
Output is correct |
| 2 |
Correct |
116 ms |
56996 KB |
Output is correct |
| 3 |
Correct |
51 ms |
51532 KB |
Output is correct |
| 4 |
Correct |
96 ms |
56776 KB |
Output is correct |
| 5 |
Correct |
91 ms |
56708 KB |
Output is correct |
| 6 |
Correct |
93 ms |
55504 KB |
Output is correct |
| 7 |
Correct |
109 ms |
56780 KB |
Output is correct |
| 8 |
Correct |
96 ms |
56932 KB |
Output is correct |
| 9 |
Correct |
50 ms |
51532 KB |
Output is correct |
| 10 |
Correct |
62 ms |
51672 KB |
Output is correct |
