#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++)
{
vector<int> mi, mx;
for(int j = mid-1;j<pos[i].size();j++)
{
int posl = pos[i][j-mid+1];
auto segl = get1(0,posl-1);
mi.pb(segl.fi);
}
for(int j = 0;j<pos[i].size();j++)
upd(pos[i][j],n,-2,-2);
for(int j = mid-1;j<pos[i].size();j++)
{
int posl = pos[i][j-mid+1];
auto segl = get1(0,posl-1);
mx.pb(segl.se);
}
for(int j = 0;j<pos[i].size();j++)
upd(pos[i][j],n,0,2);
for(int j = mid-1;j<pos[i].size();j++)
{
int ind = j-(mid-1), posr = pos[i][j];
auto segr = get1(posr,n);
int l = segr.fi-mx[ind], r = segr.se-mi[ind];
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:89:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | for(int j = mid-1;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:95:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int j = 0;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
97 | for(int j = mid-1;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:103:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j = 0;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:105:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int j = mid-1;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:113:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
113 | for(int j = 0;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
12064 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12060 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
5 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
12064 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12060 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
5 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
22 ms |
12212 KB |
Output is correct |
14 |
Correct |
21 ms |
12128 KB |
Output is correct |
15 |
Correct |
21 ms |
12116 KB |
Output is correct |
16 |
Correct |
21 ms |
12208 KB |
Output is correct |
17 |
Correct |
21 ms |
12212 KB |
Output is correct |
18 |
Correct |
19 ms |
12204 KB |
Output is correct |
19 |
Correct |
21 ms |
12116 KB |
Output is correct |
20 |
Correct |
21 ms |
12224 KB |
Output is correct |
21 |
Correct |
23 ms |
12232 KB |
Output is correct |
22 |
Correct |
23 ms |
12208 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Execution timed out |
2094 ms |
57152 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
11988 KB |
Output is correct |
2 |
Execution timed out |
2066 ms |
49500 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2072 ms |
62796 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
12064 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12060 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
5 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
22 ms |
12212 KB |
Output is correct |
14 |
Correct |
21 ms |
12128 KB |
Output is correct |
15 |
Correct |
21 ms |
12116 KB |
Output is correct |
16 |
Correct |
21 ms |
12208 KB |
Output is correct |
17 |
Correct |
21 ms |
12212 KB |
Output is correct |
18 |
Correct |
19 ms |
12204 KB |
Output is correct |
19 |
Correct |
21 ms |
12116 KB |
Output is correct |
20 |
Correct |
21 ms |
12224 KB |
Output is correct |
21 |
Correct |
23 ms |
12232 KB |
Output is correct |
22 |
Correct |
23 ms |
12208 KB |
Output is correct |
23 |
Correct |
1524 ms |
19284 KB |
Output is correct |
24 |
Correct |
1615 ms |
19284 KB |
Output is correct |
25 |
Correct |
1695 ms |
19292 KB |
Output is correct |
26 |
Correct |
1423 ms |
18352 KB |
Output is correct |
27 |
Correct |
1612 ms |
18360 KB |
Output is correct |
28 |
Correct |
1424 ms |
18360 KB |
Output is correct |
29 |
Correct |
1128 ms |
18104 KB |
Output is correct |
30 |
Correct |
1164 ms |
18160 KB |
Output is correct |
31 |
Correct |
1006 ms |
18508 KB |
Output is correct |
32 |
Correct |
1223 ms |
20200 KB |
Output is correct |
33 |
Correct |
1275 ms |
19176 KB |
Output is correct |
34 |
Correct |
1519 ms |
19100 KB |
Output is correct |
35 |
Correct |
1394 ms |
19076 KB |
Output is correct |
36 |
Correct |
1331 ms |
19196 KB |
Output is correct |
37 |
Correct |
1477 ms |
19216 KB |
Output is correct |
38 |
Correct |
1589 ms |
19252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
5 ms |
11988 KB |
Output is correct |
3 |
Correct |
5 ms |
11988 KB |
Output is correct |
4 |
Correct |
6 ms |
12064 KB |
Output is correct |
5 |
Correct |
6 ms |
11988 KB |
Output is correct |
6 |
Correct |
6 ms |
12060 KB |
Output is correct |
7 |
Correct |
6 ms |
11988 KB |
Output is correct |
8 |
Correct |
6 ms |
11988 KB |
Output is correct |
9 |
Correct |
5 ms |
11988 KB |
Output is correct |
10 |
Correct |
5 ms |
11988 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
11988 KB |
Output is correct |
13 |
Correct |
22 ms |
12212 KB |
Output is correct |
14 |
Correct |
21 ms |
12128 KB |
Output is correct |
15 |
Correct |
21 ms |
12116 KB |
Output is correct |
16 |
Correct |
21 ms |
12208 KB |
Output is correct |
17 |
Correct |
21 ms |
12212 KB |
Output is correct |
18 |
Correct |
19 ms |
12204 KB |
Output is correct |
19 |
Correct |
21 ms |
12116 KB |
Output is correct |
20 |
Correct |
21 ms |
12224 KB |
Output is correct |
21 |
Correct |
23 ms |
12232 KB |
Output is correct |
22 |
Correct |
23 ms |
12208 KB |
Output is correct |
23 |
Execution timed out |
2094 ms |
57152 KB |
Time limit exceeded |
24 |
Halted |
0 ms |
0 KB |
- |