#include <bits/stdc++.h>
#include "sequence.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 5e5+5;
struct node
{
int c[2], lzy[2];
node operator +(node t)
{
node ret;
ret.c[0]=min(c[0],t.c[0]);
ret.c[1]=max(c[1],t.c[1]);
ret.lzy[0]=ret.lzy[1]=0;
return ret;
}
};
vector<int> pos[N];
node segt[4*N];
int n;
void init()
{
for(int i = 0;i<4*n;i++)
segt[i]={0,0,0,0};
}
bool cmp(int a, int b)
{
return a<b;
}
void updlzy(int pos, int siz)
{
for(int i = 0;i<2;i++)
{
int &lzy = segt[pos].lzy[i];
if(lzy)
{
segt[pos].c[i]+=lzy;
if(siz>1)
segt[pos*2].lzy[i]+=lzy,
segt[pos*2+1].lzy[i]+=lzy;
lzy=0;
}
}
}
void upd(int lb, int rb, int val1, int val2, int l = 0, int r = n, int pos = 1)
{
updlzy(pos,r-l+1);
if(rb<l||r<lb)
return;
if(lb<=l&&r<=rb)
segt[pos].lzy[0]+=val1,
segt[pos].lzy[1]+=val2,
updlzy(pos,r-l+1);
else
{
int mid = (l+r)/2;
upd(lb,rb,val1,val2,l,mid,pos*2);
upd(lb,rb,val1,val2,mid+1,r,pos*2+1);
segt[pos]=segt[pos*2]+segt[pos*2+1];
}
}
pair<int,int> get1(int lb, int rb, int l = 0, int r = n, int pos = 1)
{
if(rb<l||r<lb)
return {1e9,-1e9};
updlzy(pos,r-l+1);
if(lb<=l&&r<=rb)
return {segt[pos].c[0],segt[pos].c[1]};
int mid = (l+r)/2;
auto t1 = get1(lb,rb,l,mid,pos*2), t2 = get1(lb,rb,mid+1,r,pos*2+1);
return {min(t1.fi,t2.fi),max(t1.se,t2.se)};
}
bool check(int n, vector<int> &a, int mid)
{
init();
for(int i = 1;i<=n;i++)
upd(i,n,1,1);
for(int i = 1;i<=n;i++)
{
for(int j = 0;j<pos[i].size();j++)
upd(pos[i][j],n,-2,0);
for(int j = mid-1;j<pos[i].size();j++)
{
int posl = pos[i][j-mid+1], posr = pos[i][j];
auto segl = get1(0,posl-1), segr = get1(posr,n);
int l = segr.fi-segl.se, r = segr.se-segl.fi;
if(l<=0&&0<=r)
return 1;
}
for(int j = 0;j<pos[i].size();j++)
upd(pos[i][j],n,0,-2);
}
return 0;
}
int sequence(int n1, vector<int> a)
{
n=n1;
for(int i = 0;i<n;i++)
pos[a[i]].pb(i+1);
int l = 1, r = n;
while(l<r)
{
int mid = (l+r+1)/2;
if(check(n,a,mid))
l=mid;
else
r=mid-1;
}
return l;
}
Compilation message
sequence.cpp: In function 'bool check(int, std::vector<int>&, int)':
sequence.cpp:88:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int j = 0;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:90:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int j = mid-1;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:98:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
98 | for(int j = 0;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
12016 KB |
Output is correct |
| 2 |
Execution timed out |
2047 ms |
49388 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2035 ms |
62880 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11988 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
