#include <bits/stdc++.h>
#include "sequence.h"
using namespace std;
struct qj{
int l,r;
friend qj operator+(qj a,qj b){
a.l+=b.l;a.r+=b.r;
return a;
}
};
struct node{
int l,r,sl,is;
qj it,iq,h,q,t;
}p[2000005];
vector<int>wz[500005];
int res,n;
void upset(int x){
p[x].t.l=p[x<<1].t.l+p[x<<1|1].t.l;
p[x].t.r=p[x<<1].t.r+p[x<<1|1].t.r;
p[x].q.l=min(p[x<<1].q.l,p[x<<1|1].q.l+p[x<<1].t.l);
p[x].q.r=max(p[x<<1].q.r,p[x<<1|1].q.r+p[x<<1].t.r);
p[x].h.l=min(p[x<<1|1].h.l,p[x<<1].h.l+p[x<<1|1].t.l);
p[x].h.r=max(p[x<<1|1].h.r,p[x<<1].h.r+p[x<<1|1].t.r);
p[x].sl=p[x<<1].sl+p[x<<1|1].sl;
}
void reset(int x,int l,int r){
p[x].l=l,p[x].r=r;
if(l==r){
p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=1;
return;
}
int mid=l+r>>1;
reset(x<<1,l,mid);
reset(x<<1|1,mid+1,r);
upset(x);
}
void sets(int x,int d,int sum){
if(p[x].l==d&&p[x].r==d){
if(sum){
p[x].h.l=p[x].h.r=p[x].q.l=p[x].q.r=p[x].t.l=p[x].t.r=sum;
p[x].sl=0;
}else{
p[x].h.l=p[x].q.l=p[x].t.l=-1;
p[x].h.r=p[x].q.r=p[x].t.r=1;
p[x].sl=1;
}
return;
}
int mid=p[x].l+p[x].r>>1;
if(d<=mid)sets(x<<1,d,sum);
else sets(x<<1|1,d,sum);
upset(x);
}
void gx(int x,int sum){
for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
}
qj gets1(int x,int d){
if(d==0)return (qj){0,0};
if(p[x].l==p[x].r){
p[x].it=p[x].t;
return p[x].t;
}
int mid=p[x].l+p[x].r>>1;
qj res=(qj){0,0};
if(d<=mid){
qj nww=gets1(x<<1,d);
p[x].it=p[x<<1].it;
return nww;
}else{
qj rr=gets1(x<<1|1,d);
res.l=min(rr.l,p[x<<1|1].it.l+p[x<<1].h.l);
res.r=max(rr.r,p[x<<1|1].it.r+p[x<<1].h.r);
p[x].it=p[x<<1].t+p[x<<1|1].it;
}
return res;
}
void init(int x,int d){
if(p[x].l==p[x].r){
p[x].it=p[x].t,p[x].iq=p[x].q,p[x].is=p[x].sl;
return;
}
if(p[x<<1].r<d){
init(x<<1|1,d);
p[x].it=p[x<<1|1].it,p[x].iq=p[x<<1|1].iq,p[x].is=p[x<<1|1].is;
return;
}
init(x<<1,d);
p[x].it=p[x<<1].it+p[x<<1|1].t;
p[x].iq.l=min(p[x<<1].iq.l,p[x<<1|1].q.l+p[x<<1].it.l);
p[x].iq.r=max(p[x<<1].iq.r,p[x<<1|1].q.r+p[x<<1].it.r);
p[x].is=p[x<<1].is+p[x<<1|1].sl;
}
int gets(int x,int d,qj sum,int ans,int xy){
if(p[x].l==p[x].r)return ans+p[x].sl;
int mid=p[x].l+p[x].r>>1;
if(d>mid)return gets(x<<1|1,d,sum,ans,1);
if(xy){
qj rt=p[x<<1].it+p[x<<1|1].q+sum;
if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].it,ans+p[x<<1].is,0);
else return gets(x<<1,d,sum,ans,1);
}else{
qj rt=p[x<<1].t+p[x<<1|1].q+sum;
if(rt.l<=0&&rt.r>=0)return gets(x<<1|1,d,sum+p[x<<1].t,ans+p[x<<1].sl,0);
else return gets(x<<1,d,sum,ans,0);
}
}
int sol(int x){
qj fw=gets1(1,x-1);
fw.l=min(0,fw.l),fw.r=max(fw.r,0);
init(1,x);
return gets(1,x,fw,0,1);
}
int solve(int x){
int ans=0;
for(int i=0;i<wz[x].size();i++){
ans=max(ans,sol(wz[x][i]));
}
return ans;
}
int sequence(int N,vector<int>w){
n=N;
reset(1,1,n);
for(int i=0;i<n;i++){
wz[w[i]].push_back(i+1);
}
for(int i=1;i<=n;i++){
gx(i-1,-1);
gx(i,0);
gx(i+1,1);
res=max(res,solve(i));
}
return res;
}
Compilation message
sequence.cpp: In function 'void reset(int, int, int)':
sequence.cpp:32:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
32 | int mid=l+r>>1;
| ~^~
sequence.cpp: In function 'void sets(int, int, int)':
sequence.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
49 | int mid=p[x].l+p[x].r>>1;
| ~~~~~~^~~~~~~
sequence.cpp: In function 'void gx(int, int)':
sequence.cpp:55:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<wz[x].size();i++)sets(1,wz[x][i],sum);
| ~^~~~~~~~~~~~~
sequence.cpp: In function 'qj gets1(int, int)':
sequence.cpp:63:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int mid=p[x].l+p[x].r>>1;
| ~~~~~~^~~~~~~
sequence.cpp: In function 'int gets(int, int, qj, int, int)':
sequence.cpp:95:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
95 | int mid=p[x].l+p[x].r>>1;
| ~~~~~~^~~~~~~
sequence.cpp: In function 'int solve(int)':
sequence.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
115 | for(int i=0;i<wz[x].size();i++){
| ~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12048 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12012 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 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 |
6 ms |
12020 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12072 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12048 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12012 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 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 |
6 ms |
12020 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12072 KB |
Output is correct |
13 |
Correct |
8 ms |
12244 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
9 ms |
12244 KB |
Output is correct |
18 |
Correct |
8 ms |
12328 KB |
Output is correct |
19 |
Correct |
9 ms |
12244 KB |
Output is correct |
20 |
Correct |
10 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12248 KB |
Output is correct |
22 |
Correct |
9 ms |
12244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12048 KB |
Output is correct |
2 |
Correct |
648 ms |
83232 KB |
Output is correct |
3 |
Correct |
646 ms |
83216 KB |
Output is correct |
4 |
Correct |
575 ms |
75448 KB |
Output is correct |
5 |
Correct |
638 ms |
82496 KB |
Output is correct |
6 |
Correct |
654 ms |
82400 KB |
Output is correct |
7 |
Correct |
626 ms |
75788 KB |
Output is correct |
8 |
Correct |
573 ms |
75980 KB |
Output is correct |
9 |
Correct |
548 ms |
76128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
11988 KB |
Output is correct |
2 |
Correct |
560 ms |
76540 KB |
Output is correct |
3 |
Correct |
564 ms |
75552 KB |
Output is correct |
4 |
Correct |
559 ms |
75568 KB |
Output is correct |
5 |
Correct |
584 ms |
76524 KB |
Output is correct |
6 |
Correct |
551 ms |
75600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
921 ms |
89076 KB |
Output is correct |
2 |
Correct |
920 ms |
89060 KB |
Output is correct |
3 |
Correct |
928 ms |
88524 KB |
Output is correct |
4 |
Correct |
923 ms |
88496 KB |
Output is correct |
5 |
Correct |
775 ms |
85080 KB |
Output is correct |
6 |
Correct |
766 ms |
85196 KB |
Output is correct |
7 |
Correct |
576 ms |
84020 KB |
Output is correct |
8 |
Correct |
579 ms |
83644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12048 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12012 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 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 |
6 ms |
12020 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12072 KB |
Output is correct |
13 |
Correct |
8 ms |
12244 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
9 ms |
12244 KB |
Output is correct |
18 |
Correct |
8 ms |
12328 KB |
Output is correct |
19 |
Correct |
9 ms |
12244 KB |
Output is correct |
20 |
Correct |
10 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12248 KB |
Output is correct |
22 |
Correct |
9 ms |
12244 KB |
Output is correct |
23 |
Correct |
146 ms |
28628 KB |
Output is correct |
24 |
Correct |
143 ms |
28628 KB |
Output is correct |
25 |
Correct |
142 ms |
28624 KB |
Output is correct |
26 |
Correct |
147 ms |
27704 KB |
Output is correct |
27 |
Correct |
134 ms |
27708 KB |
Output is correct |
28 |
Correct |
133 ms |
27660 KB |
Output is correct |
29 |
Correct |
102 ms |
27348 KB |
Output is correct |
30 |
Correct |
106 ms |
27500 KB |
Output is correct |
31 |
Correct |
92 ms |
27608 KB |
Output is correct |
32 |
Correct |
95 ms |
29548 KB |
Output is correct |
33 |
Correct |
138 ms |
28416 KB |
Output is correct |
34 |
Correct |
142 ms |
28348 KB |
Output is correct |
35 |
Correct |
134 ms |
28372 KB |
Output is correct |
36 |
Correct |
148 ms |
28396 KB |
Output is correct |
37 |
Correct |
139 ms |
28408 KB |
Output is correct |
38 |
Correct |
139 ms |
28452 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
12048 KB |
Output is correct |
2 |
Correct |
6 ms |
11988 KB |
Output is correct |
3 |
Correct |
7 ms |
11988 KB |
Output is correct |
4 |
Correct |
7 ms |
12012 KB |
Output is correct |
5 |
Correct |
7 ms |
12116 KB |
Output is correct |
6 |
Correct |
6 ms |
11988 KB |
Output is correct |
7 |
Correct |
6 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 |
6 ms |
12020 KB |
Output is correct |
11 |
Correct |
6 ms |
11988 KB |
Output is correct |
12 |
Correct |
7 ms |
12072 KB |
Output is correct |
13 |
Correct |
8 ms |
12244 KB |
Output is correct |
14 |
Correct |
8 ms |
12244 KB |
Output is correct |
15 |
Correct |
8 ms |
12244 KB |
Output is correct |
16 |
Correct |
8 ms |
12244 KB |
Output is correct |
17 |
Correct |
9 ms |
12244 KB |
Output is correct |
18 |
Correct |
8 ms |
12328 KB |
Output is correct |
19 |
Correct |
9 ms |
12244 KB |
Output is correct |
20 |
Correct |
10 ms |
12244 KB |
Output is correct |
21 |
Correct |
8 ms |
12248 KB |
Output is correct |
22 |
Correct |
9 ms |
12244 KB |
Output is correct |
23 |
Correct |
648 ms |
83232 KB |
Output is correct |
24 |
Correct |
646 ms |
83216 KB |
Output is correct |
25 |
Correct |
575 ms |
75448 KB |
Output is correct |
26 |
Correct |
638 ms |
82496 KB |
Output is correct |
27 |
Correct |
654 ms |
82400 KB |
Output is correct |
28 |
Correct |
626 ms |
75788 KB |
Output is correct |
29 |
Correct |
573 ms |
75980 KB |
Output is correct |
30 |
Correct |
548 ms |
76128 KB |
Output is correct |
31 |
Correct |
560 ms |
76540 KB |
Output is correct |
32 |
Correct |
564 ms |
75552 KB |
Output is correct |
33 |
Correct |
559 ms |
75568 KB |
Output is correct |
34 |
Correct |
584 ms |
76524 KB |
Output is correct |
35 |
Correct |
551 ms |
75600 KB |
Output is correct |
36 |
Correct |
921 ms |
89076 KB |
Output is correct |
37 |
Correct |
920 ms |
89060 KB |
Output is correct |
38 |
Correct |
928 ms |
88524 KB |
Output is correct |
39 |
Correct |
923 ms |
88496 KB |
Output is correct |
40 |
Correct |
775 ms |
85080 KB |
Output is correct |
41 |
Correct |
766 ms |
85196 KB |
Output is correct |
42 |
Correct |
576 ms |
84020 KB |
Output is correct |
43 |
Correct |
579 ms |
83644 KB |
Output is correct |
44 |
Correct |
146 ms |
28628 KB |
Output is correct |
45 |
Correct |
143 ms |
28628 KB |
Output is correct |
46 |
Correct |
142 ms |
28624 KB |
Output is correct |
47 |
Correct |
147 ms |
27704 KB |
Output is correct |
48 |
Correct |
134 ms |
27708 KB |
Output is correct |
49 |
Correct |
133 ms |
27660 KB |
Output is correct |
50 |
Correct |
102 ms |
27348 KB |
Output is correct |
51 |
Correct |
106 ms |
27500 KB |
Output is correct |
52 |
Correct |
92 ms |
27608 KB |
Output is correct |
53 |
Correct |
95 ms |
29548 KB |
Output is correct |
54 |
Correct |
138 ms |
28416 KB |
Output is correct |
55 |
Correct |
142 ms |
28348 KB |
Output is correct |
56 |
Correct |
134 ms |
28372 KB |
Output is correct |
57 |
Correct |
148 ms |
28396 KB |
Output is correct |
58 |
Correct |
139 ms |
28408 KB |
Output is correct |
59 |
Correct |
139 ms |
28452 KB |
Output is correct |
60 |
Correct |
1128 ms |
83336 KB |
Output is correct |
61 |
Correct |
1134 ms |
83336 KB |
Output is correct |
62 |
Correct |
1148 ms |
83352 KB |
Output is correct |
63 |
Correct |
1089 ms |
76624 KB |
Output is correct |
64 |
Correct |
1157 ms |
76616 KB |
Output is correct |
65 |
Correct |
1088 ms |
76604 KB |
Output is correct |
66 |
Correct |
623 ms |
75656 KB |
Output is correct |
67 |
Correct |
632 ms |
75788 KB |
Output is correct |
68 |
Correct |
578 ms |
75560 KB |
Output is correct |
69 |
Correct |
595 ms |
89072 KB |
Output is correct |
70 |
Correct |
1069 ms |
82428 KB |
Output is correct |
71 |
Correct |
1050 ms |
82232 KB |
Output is correct |
72 |
Correct |
1088 ms |
81808 KB |
Output is correct |
73 |
Correct |
1051 ms |
82120 KB |
Output is correct |
74 |
Correct |
1075 ms |
81732 KB |
Output is correct |
75 |
Correct |
1092 ms |
82104 KB |
Output is correct |