#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
const int maxn=5e5+9;
struct IT_lazy{
int mx[maxn<<2],mn[maxn<<2],lazy[maxn<<2];
void resz(int n){
for1(i,1,4*n)mx[i]=mn[i]=lazy[i]=0;
}
void push(int id){
if (lazy[id]){
mx[id<<1]+=lazy[id];
mx[id<<1|1]+=lazy[id];
mn[id<<1]+=lazy[id];
mn[id<<1|1]+=lazy[id];
lazy[id<<1]+=lazy[id];
lazy[id<<1|1]+=lazy[id];
lazy[id]=0;
}
}
void update(int id,int l,int r,int u,int v,int val){
if (l>v||r<u||u>v)return;
if (u<=l&&r<=v){
mx[id]+=val;
mn[id]+=val;
lazy[id]+=val;
return;
}
push(id);
int mid=(l+r)>>1;
update(id<<1,l,mid,u,v,val);
update(id<<1|1,mid+1,r,u,v,val);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
}
int get_max(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return -maxn;
if (u<=l&&r<=v)return mx[id];
int mid=(l+r)>>1;
push(id);
return max(get_max(id<<1,l,mid,u,v),get_max(id<<1|1,mid+1,r,u,v));
}
int get_min(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return maxn;
if (u<=l&&r<=v)return mn[id];
int mid=(l+r)>>1;
push(id);
return min(get_min(id<<1,l,mid,u,v),get_min(id<<1|1,mid+1,r,u,v));
}
};
struct IT{
int st[maxn*4];
void update(int id,int l,int r,int u,int val){
if(l>u||r<u)return;
if (l==r){
st[id]=val;
return;
}
int mid=(l+r)>>1;
if (mid>=u)update(id<<1,l,mid,u,val);
else update(id<<1|1,mid+1,r,u,val);
st[id]=max(st[id<<1],st[id<<1|1]);
}
int walk(int id,int l,int r,int val){
if (st[id]<val)return -1;
if (l==r)return l;
int mid=(l+r)>>1;
int ans=walk(id<<1,l,mid,val);
if (ans==-1)return walk(id<<1|1,mid+1,r,val);
return ans;
}
};
int n;
int a[maxn];
vector<int>value[maxn];
int mx_l[maxn],mn_l[maxn],mn_r[maxn],mx_r[maxn];
int pf[maxn];
void pre(){
IT_lazy st;
st.resz(n);
auto up=[&](int id,int val){
st.update(1,1,n,id,n,val);
};
for1(i,1,n)up(i,-1);
for1(i,1,n){
for (auto v:value[i]){
up(v,2);
}
for (auto v:value[i]){
pf[v]=st.get_max(1,1,n,v,v);
}
for1(j,0,sz(value[i])-1){
int v=value[i][j];
if (j==sz(value[i])-1)mx_r[v]=st.get_max(1,1,n,v,n)-pf[v],mn_r[v]=st.get_min(1,1,n,v,n)-pf[v];
else mx_r[v]=st.get_max(1,1,n,v,value[i][j+1]-1)-pf[v],mn_r[v]=st.get_min(1,1,n,v,value[i][j+1]-1)-pf[v];
}
}
st.resz(n);
auto rup=[&](int id,int val){
st.update(1,1,n,1,id,val);
};
for1(i,1,n)rup(i,-1);
for1(i,1,n){
for (auto v:value[i])rup(v,2);
for1(j,0,sz(value[i])-1){
int v=value[i][j];
int suffix=st.get_max(1,1,n,v,v);
if (j==0){
mx_l[v]=st.get_max(1,1,n,1,v)-suffix,mn_l[v]=st.get_min(1,1,n,1,v)-suffix;
}
else {
mx_l[v]=st.get_max(1,1,n,value[i][j-1]+1,v)-suffix,mn_l[v]=st.get_min(1,1,n,value[i][j-1]+1,v)-suffix;
}
}
}
}
struct type{
int id,val;
bool fl;
bool operator < (const type &p){
if (val==p.val)return fl<p.fl;
return val<p.val;
}
};
int sequence(int N, std::vector<int> A) {
n=N;
for1(i,1,n)a[i]=A[i-1];
for1(i,1,n)value[a[i]].pb(i);
int ans=0;
pre();
IT st;
for1(i,1,n){
vector<type>t;
for1(j,0,sz(value[i])-1){
int v=value[i][j];
t.pb({j+1,pf[v]-mx_l[v],0});
t.pb({j+1,pf[v]+1+mx_r[v],1});
}
sort(all(t));
int m=sz(value[i]);
for1(j,1,4*m)st.st[j]=-n*10;
for (auto v:t){
int id=value[i][v.id-1];
if (v.fl==0){
st.update(1,1,m,v.id,pf[id]-mn_l[id]-2*v.id);
}
else {
int pos=st.walk(1,1,m,pf[id]+1+mn_r[id]-2*v.id-2);
if (pos!=-1&&pos<=v.id){
ans=max(ans,v.id-pos+1);
}
}
}
}
return ans;
}
/*signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("temp.INP","r",stdin);
//freopen(".OUT","w",stdout);
int N;
assert(1 == scanf("%d", &N));
std::vector<int> A(N);
for (int i = 0; i < N; ++i) {
assert(1 == scanf("%d", &A[i]));
}
int result = sequence(N, A);
printf("%d\n", result);
return 0;
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
54092 KB |
Output is correct |
2 |
Correct |
25 ms |
54100 KB |
Output is correct |
3 |
Correct |
25 ms |
54100 KB |
Output is correct |
4 |
Correct |
26 ms |
54100 KB |
Output is correct |
5 |
Correct |
25 ms |
54104 KB |
Output is correct |
6 |
Correct |
26 ms |
54224 KB |
Output is correct |
7 |
Correct |
27 ms |
54176 KB |
Output is correct |
8 |
Correct |
26 ms |
54080 KB |
Output is correct |
9 |
Correct |
25 ms |
54104 KB |
Output is correct |
10 |
Correct |
25 ms |
54264 KB |
Output is correct |
11 |
Correct |
26 ms |
54288 KB |
Output is correct |
12 |
Correct |
30 ms |
54212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
54092 KB |
Output is correct |
2 |
Correct |
25 ms |
54100 KB |
Output is correct |
3 |
Correct |
25 ms |
54100 KB |
Output is correct |
4 |
Correct |
26 ms |
54100 KB |
Output is correct |
5 |
Correct |
25 ms |
54104 KB |
Output is correct |
6 |
Correct |
26 ms |
54224 KB |
Output is correct |
7 |
Correct |
27 ms |
54176 KB |
Output is correct |
8 |
Correct |
26 ms |
54080 KB |
Output is correct |
9 |
Correct |
25 ms |
54104 KB |
Output is correct |
10 |
Correct |
25 ms |
54264 KB |
Output is correct |
11 |
Correct |
26 ms |
54288 KB |
Output is correct |
12 |
Correct |
30 ms |
54212 KB |
Output is correct |
13 |
Correct |
28 ms |
54364 KB |
Output is correct |
14 |
Correct |
28 ms |
54360 KB |
Output is correct |
15 |
Correct |
29 ms |
54556 KB |
Output is correct |
16 |
Correct |
30 ms |
54360 KB |
Output is correct |
17 |
Correct |
28 ms |
54224 KB |
Output is correct |
18 |
Correct |
31 ms |
54416 KB |
Output is correct |
19 |
Correct |
28 ms |
54404 KB |
Output is correct |
20 |
Correct |
28 ms |
54252 KB |
Output is correct |
21 |
Correct |
28 ms |
54364 KB |
Output is correct |
22 |
Correct |
28 ms |
54388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
54092 KB |
Output is correct |
2 |
Correct |
796 ms |
70944 KB |
Output is correct |
3 |
Correct |
863 ms |
70996 KB |
Output is correct |
4 |
Correct |
804 ms |
67472 KB |
Output is correct |
5 |
Correct |
841 ms |
69916 KB |
Output is correct |
6 |
Correct |
796 ms |
69700 KB |
Output is correct |
7 |
Correct |
797 ms |
63252 KB |
Output is correct |
8 |
Correct |
778 ms |
63280 KB |
Output is correct |
9 |
Correct |
792 ms |
73260 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
25 ms |
54100 KB |
Output is correct |
2 |
Correct |
844 ms |
75960 KB |
Output is correct |
3 |
Correct |
894 ms |
73176 KB |
Output is correct |
4 |
Correct |
861 ms |
74076 KB |
Output is correct |
5 |
Correct |
856 ms |
81212 KB |
Output is correct |
6 |
Correct |
822 ms |
73868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1145 ms |
76504 KB |
Output is correct |
2 |
Correct |
1202 ms |
76656 KB |
Output is correct |
3 |
Correct |
1200 ms |
76260 KB |
Output is correct |
4 |
Correct |
1172 ms |
76020 KB |
Output is correct |
5 |
Correct |
978 ms |
72664 KB |
Output is correct |
6 |
Correct |
1036 ms |
72664 KB |
Output is correct |
7 |
Correct |
860 ms |
71468 KB |
Output is correct |
8 |
Correct |
863 ms |
71152 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
54092 KB |
Output is correct |
2 |
Correct |
25 ms |
54100 KB |
Output is correct |
3 |
Correct |
25 ms |
54100 KB |
Output is correct |
4 |
Correct |
26 ms |
54100 KB |
Output is correct |
5 |
Correct |
25 ms |
54104 KB |
Output is correct |
6 |
Correct |
26 ms |
54224 KB |
Output is correct |
7 |
Correct |
27 ms |
54176 KB |
Output is correct |
8 |
Correct |
26 ms |
54080 KB |
Output is correct |
9 |
Correct |
25 ms |
54104 KB |
Output is correct |
10 |
Correct |
25 ms |
54264 KB |
Output is correct |
11 |
Correct |
26 ms |
54288 KB |
Output is correct |
12 |
Correct |
30 ms |
54212 KB |
Output is correct |
13 |
Correct |
28 ms |
54364 KB |
Output is correct |
14 |
Correct |
28 ms |
54360 KB |
Output is correct |
15 |
Correct |
29 ms |
54556 KB |
Output is correct |
16 |
Correct |
30 ms |
54360 KB |
Output is correct |
17 |
Correct |
28 ms |
54224 KB |
Output is correct |
18 |
Correct |
31 ms |
54416 KB |
Output is correct |
19 |
Correct |
28 ms |
54404 KB |
Output is correct |
20 |
Correct |
28 ms |
54252 KB |
Output is correct |
21 |
Correct |
28 ms |
54364 KB |
Output is correct |
22 |
Correct |
28 ms |
54388 KB |
Output is correct |
23 |
Correct |
191 ms |
57140 KB |
Output is correct |
24 |
Correct |
204 ms |
56916 KB |
Output is correct |
25 |
Correct |
204 ms |
57172 KB |
Output is correct |
26 |
Correct |
177 ms |
55892 KB |
Output is correct |
27 |
Correct |
180 ms |
55884 KB |
Output is correct |
28 |
Correct |
175 ms |
55888 KB |
Output is correct |
29 |
Correct |
144 ms |
56356 KB |
Output is correct |
30 |
Correct |
153 ms |
56268 KB |
Output is correct |
31 |
Correct |
136 ms |
59296 KB |
Output is correct |
32 |
Correct |
126 ms |
58064 KB |
Output is correct |
33 |
Correct |
227 ms |
57416 KB |
Output is correct |
34 |
Correct |
192 ms |
57416 KB |
Output is correct |
35 |
Correct |
184 ms |
57248 KB |
Output is correct |
36 |
Correct |
179 ms |
57360 KB |
Output is correct |
37 |
Correct |
200 ms |
57384 KB |
Output is correct |
38 |
Correct |
203 ms |
57364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
54092 KB |
Output is correct |
2 |
Correct |
25 ms |
54100 KB |
Output is correct |
3 |
Correct |
25 ms |
54100 KB |
Output is correct |
4 |
Correct |
26 ms |
54100 KB |
Output is correct |
5 |
Correct |
25 ms |
54104 KB |
Output is correct |
6 |
Correct |
26 ms |
54224 KB |
Output is correct |
7 |
Correct |
27 ms |
54176 KB |
Output is correct |
8 |
Correct |
26 ms |
54080 KB |
Output is correct |
9 |
Correct |
25 ms |
54104 KB |
Output is correct |
10 |
Correct |
25 ms |
54264 KB |
Output is correct |
11 |
Correct |
26 ms |
54288 KB |
Output is correct |
12 |
Correct |
30 ms |
54212 KB |
Output is correct |
13 |
Correct |
28 ms |
54364 KB |
Output is correct |
14 |
Correct |
28 ms |
54360 KB |
Output is correct |
15 |
Correct |
29 ms |
54556 KB |
Output is correct |
16 |
Correct |
30 ms |
54360 KB |
Output is correct |
17 |
Correct |
28 ms |
54224 KB |
Output is correct |
18 |
Correct |
31 ms |
54416 KB |
Output is correct |
19 |
Correct |
28 ms |
54404 KB |
Output is correct |
20 |
Correct |
28 ms |
54252 KB |
Output is correct |
21 |
Correct |
28 ms |
54364 KB |
Output is correct |
22 |
Correct |
28 ms |
54388 KB |
Output is correct |
23 |
Correct |
796 ms |
70944 KB |
Output is correct |
24 |
Correct |
863 ms |
70996 KB |
Output is correct |
25 |
Correct |
804 ms |
67472 KB |
Output is correct |
26 |
Correct |
841 ms |
69916 KB |
Output is correct |
27 |
Correct |
796 ms |
69700 KB |
Output is correct |
28 |
Correct |
797 ms |
63252 KB |
Output is correct |
29 |
Correct |
778 ms |
63280 KB |
Output is correct |
30 |
Correct |
792 ms |
73260 KB |
Output is correct |
31 |
Correct |
844 ms |
75960 KB |
Output is correct |
32 |
Correct |
894 ms |
73176 KB |
Output is correct |
33 |
Correct |
861 ms |
74076 KB |
Output is correct |
34 |
Correct |
856 ms |
81212 KB |
Output is correct |
35 |
Correct |
822 ms |
73868 KB |
Output is correct |
36 |
Correct |
1145 ms |
76504 KB |
Output is correct |
37 |
Correct |
1202 ms |
76656 KB |
Output is correct |
38 |
Correct |
1200 ms |
76260 KB |
Output is correct |
39 |
Correct |
1172 ms |
76020 KB |
Output is correct |
40 |
Correct |
978 ms |
72664 KB |
Output is correct |
41 |
Correct |
1036 ms |
72664 KB |
Output is correct |
42 |
Correct |
860 ms |
71468 KB |
Output is correct |
43 |
Correct |
863 ms |
71152 KB |
Output is correct |
44 |
Correct |
191 ms |
57140 KB |
Output is correct |
45 |
Correct |
204 ms |
56916 KB |
Output is correct |
46 |
Correct |
204 ms |
57172 KB |
Output is correct |
47 |
Correct |
177 ms |
55892 KB |
Output is correct |
48 |
Correct |
180 ms |
55884 KB |
Output is correct |
49 |
Correct |
175 ms |
55888 KB |
Output is correct |
50 |
Correct |
144 ms |
56356 KB |
Output is correct |
51 |
Correct |
153 ms |
56268 KB |
Output is correct |
52 |
Correct |
136 ms |
59296 KB |
Output is correct |
53 |
Correct |
126 ms |
58064 KB |
Output is correct |
54 |
Correct |
227 ms |
57416 KB |
Output is correct |
55 |
Correct |
192 ms |
57416 KB |
Output is correct |
56 |
Correct |
184 ms |
57248 KB |
Output is correct |
57 |
Correct |
179 ms |
57360 KB |
Output is correct |
58 |
Correct |
200 ms |
57384 KB |
Output is correct |
59 |
Correct |
203 ms |
57364 KB |
Output is correct |
60 |
Correct |
1859 ms |
70856 KB |
Output is correct |
61 |
Correct |
1839 ms |
72532 KB |
Output is correct |
62 |
Correct |
1809 ms |
72388 KB |
Output is correct |
63 |
Correct |
1488 ms |
64332 KB |
Output is correct |
64 |
Correct |
1625 ms |
64336 KB |
Output is correct |
65 |
Correct |
1652 ms |
64336 KB |
Output is correct |
66 |
Correct |
938 ms |
68044 KB |
Output is correct |
67 |
Correct |
874 ms |
67480 KB |
Output is correct |
68 |
Correct |
775 ms |
79292 KB |
Output is correct |
69 |
Correct |
734 ms |
78108 KB |
Output is correct |
70 |
Correct |
1612 ms |
73036 KB |
Output is correct |
71 |
Execution timed out |
2062 ms |
74728 KB |
Time limit exceeded |
72 |
Halted |
0 ms |
0 KB |
- |