#include <bits/stdc++.h>
using namespace std;
int fr[500005];
vector <int> pos[500005];
/**
1 <= l <= pos[i][j]
pos[i][j+x-1] + 1 <= r <= n
0000000****111
abs(cnt[-1]-cnt[1]) <= x
abs(cnt[1]-cnt[-1]) <= x
abs(pref[r] - pref[l]) <= x
-x <= pref[r] - pref[l] <= x
pref[l] - pref[r] <= x sau pref[r] - pref[l] <= x
[a,b]
[c,d]
[a-x,b+x] trebuie sa se intersecteze cu [c,d]
*/
struct LazySegmentTree
{
int n;
int aux[500005];
int minim[2000005];
int maxim[2000005];
int lazy[2000005];
void build(int i,int x,int y)
{
lazy[i]=0;
if(x==y)
minim[i]=maxim[i]=aux[x];
else
{
int mid=(x+y)/2;
build(2*i,x,mid);
build(2*i+1,mid+1,y);
minim[i]=min(minim[2*i],minim[2*i+1]);
maxim[i]=max(maxim[2*i],maxim[2*i+1]);
}
}
void init(int _n)
{
n=_n;
for(int i=0; i<=n; i++)
aux[i]=i;
build(1,0,n);
}
void propag(int i,int x,int y)
{
if(x!=y)
{
lazy[2*i]+=lazy[i];
lazy[2*i+1]+=lazy[i];
minim[2*i]+=lazy[i];
maxim[2*i]+=lazy[i];
minim[2*i+1]+=lazy[i];
maxim[2*i+1]+=lazy[i];
lazy[i]=0;
}
}
void update(int i,int x,int y,int l,int r,int v)
{
propag(i,x,y);
if(l<=x && y<=r)
{
lazy[i]+=v;
minim[i]+=v;
maxim[i]+=v;
propag(i,x,y);
}
else
{
int mid=(x+y)/2;
if(l<=mid)
update(2*i,x,mid,l,r,v);
if(r>mid)
update(2*i+1,mid+1,y,l,r,v);
minim[i]=min(minim[2*i],minim[2*i+1]);
maxim[i]=max(maxim[2*i],maxim[2*i+1]);
}
}
pair <int,int> query(int i,int x,int y,int l,int r)
{
propag(i,x,y);
if(l<=x && y<=r)
return make_pair(minim[i],maxim[i]);
int mid=(x+y)/2;
pair <int,int> aux=make_pair(n,-n);
if(l<=mid)
aux=query(2*i,x,mid,l,r);
if(r>mid)
{
pair <int,int> temp;
temp=query(2*i+1,mid+1,y,l,r);
aux.first=min(aux.first,temp.first);
aux.second=max(aux.second,temp.second);
}
return aux;
}
} sgt;
bool ok(int n,int x)
{
sgt.init(n);
for(int i=1; i<=n; i++)
{
for(auto it:pos[i])
sgt.update(1,0,n,it+1,n,-1);
if(fr[i]>=x)
{
for(int j=0; j+x-1<fr[i]; j++)
{
pair <int,int> aux=sgt.query(1,0,n,0,pos[i][j]);
int a=aux.first;
int b=aux.second;
aux=sgt.query(1,0,n,pos[i][j+x-1]+1,n);
int c=aux.first;
int d=aux.second;
if(max(a-x,c)<=min(b+x,d))
return 1;
}
}
for(auto it:pos[i])
sgt.update(1,0,n,it+1,n,-1);
}
return 0;
}
int sequence(int n,vector <int> a)
{
int mxfr=0;
for(int i=0; i<n; i++)
{
fr[a[i]]++;
mxfr=max(mxfr,fr[a[i]]);
pos[a[i]].push_back(i);
}
int st=1,dr=mxfr,mij;
while(st<=dr)
{
mij=(st+dr)/2;
if(ok(n,mij)==1)
st=mij+1;
else
dr=mij-1;
}
return st-1;
}
int n;
vector <int> a;
int main()
{
cin>>n;
for(int i=0; i<n; i++)
{
int x;
cin>>x;
a.push_back(x);
}
cout<<sequence(n,a)<<"\n";
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cckIIwLF.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc06wNXC.o:sequence.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
