#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;
}
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
12016 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
12016 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12116 KB |
Output is correct |
14 |
Correct |
8 ms |
12116 KB |
Output is correct |
15 |
Correct |
8 ms |
12116 KB |
Output is correct |
16 |
Correct |
9 ms |
12072 KB |
Output is correct |
17 |
Correct |
12 ms |
12160 KB |
Output is correct |
18 |
Correct |
6 ms |
12164 KB |
Output is correct |
19 |
Correct |
12 ms |
12116 KB |
Output is correct |
20 |
Correct |
12 ms |
12188 KB |
Output is correct |
21 |
Incorrect |
11 ms |
12068 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
119 ms |
42160 KB |
Output is correct |
3 |
Correct |
509 ms |
42116 KB |
Output is correct |
4 |
Execution timed out |
2076 ms |
32340 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
1360 ms |
32480 KB |
Output is correct |
3 |
Execution timed out |
2084 ms |
32344 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
456 ms |
47804 KB |
Output is correct |
2 |
Correct |
489 ms |
47872 KB |
Output is correct |
3 |
Correct |
145 ms |
47208 KB |
Output is correct |
4 |
Correct |
152 ms |
47180 KB |
Output is correct |
5 |
Correct |
253 ms |
43340 KB |
Output is correct |
6 |
Correct |
415 ms |
43452 KB |
Output is correct |
7 |
Correct |
420 ms |
42100 KB |
Output is correct |
8 |
Correct |
292 ms |
41648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
12016 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12116 KB |
Output is correct |
14 |
Correct |
8 ms |
12116 KB |
Output is correct |
15 |
Correct |
8 ms |
12116 KB |
Output is correct |
16 |
Correct |
9 ms |
12072 KB |
Output is correct |
17 |
Correct |
12 ms |
12160 KB |
Output is correct |
18 |
Correct |
6 ms |
12164 KB |
Output is correct |
19 |
Correct |
12 ms |
12116 KB |
Output is correct |
20 |
Correct |
12 ms |
12188 KB |
Output is correct |
21 |
Incorrect |
11 ms |
12068 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
6 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
11988 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
7 ms |
12016 KB |
Output is correct |
7 |
Correct |
7 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
7 ms |
11988 KB |
Output is correct |
10 |
Correct |
7 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
6 ms |
11988 KB |
Output is correct |
13 |
Correct |
8 ms |
12116 KB |
Output is correct |
14 |
Correct |
8 ms |
12116 KB |
Output is correct |
15 |
Correct |
8 ms |
12116 KB |
Output is correct |
16 |
Correct |
9 ms |
12072 KB |
Output is correct |
17 |
Correct |
12 ms |
12160 KB |
Output is correct |
18 |
Correct |
6 ms |
12164 KB |
Output is correct |
19 |
Correct |
12 ms |
12116 KB |
Output is correct |
20 |
Correct |
12 ms |
12188 KB |
Output is correct |
21 |
Incorrect |
11 ms |
12068 KB |
Output isn't correct |
22 |
Halted |
0 ms |
0 KB |
- |