#include "sequence.h"
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int readint(){
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int mn[2000005],mx[2000005],lzy[2000005],prefmn[500005],prefmx[500005],suffmn[500005],suffmx[500005];
vector<int> pos[500005];
void push(int id){
if(lzy[id]==0) return;
mn[id<<1]+=lzy[id];
mx[id<<1]+=lzy[id];
mn[id<<1|1]+=lzy[id];
mx[id<<1|1]+=lzy[id];
lzy[id<<1]+=lzy[id];
lzy[id<<1|1]+=lzy[id];
lzy[id]=0;
}
void build(int id,int l,int r){
if(l==r){
mn[id]=l;
mx[id]=l;
return;
}
int mid=(l+r)/2;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
}
void change(int id,int l,int r,int ql,int qr,int v){
if(ql<=l&&r<=qr){
lzy[id]+=v;
mn[id]+=v;
mx[id]+=v;
push(id);
return;
}
push(id);
int mid=(l+r)/2;
if(qr<=mid) change(id<<1,l,mid,ql,qr,v);
else if(ql>mid) change(id<<1|1,mid+1,r,ql,qr,v);
else change(id<<1,l,mid,ql,qr,v),change(id<<1|1,mid+1,r,ql,qr,v);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
}
pii query(int id,int l,int r,int ql,int qr){
if(l>r||l>qr||r<ql||ql>qr) return mp((int)1e9,(int)-1e9);
if(ql<=l&&r<=qr) return mp(mn[id],mx[id]);
push(id);
int mid=(l+r)/2;
pii L=query(id<<1,l,mid,ql,qr);
pii R=query(id<<1|1,mid+1,r,ql,qr);
mn[id]=min(mn[id<<1],mn[id<<1|1]);
mx[id]=max(mx[id<<1],mx[id<<1|1]);
return mp(min(L.fi,R.fi),max(L.se,R.se));
}
int sgn(int x){return (x==0?0:(x<0?-1:1));}
int sequence(int n,vector<int> a){
for(int i=1;i<=n;i++) pos[a[i-1]].pb(i);
build(1,0,n);
int ans=1;
for(int v=1;v<=n;v++){
for(int i:pos[v]) prefmn[i]=query(1,0,n,0,i-1).fi,suffmx[i]=query(1,0,n,i,n).se;
for(int i:pos[v]) change(1,0,n,i,n,-2);
for(int i:pos[v]) prefmx[i]=query(1,0,n,0,i-1).se,suffmn[i]=query(1,0,n,i,n).fi;
int ptr=0;
for(int i=0;i<pos[v].size();i++){
while(ptr+1<pos[v].size()&&sgn(suffmx[pos[v][ptr+1]]-prefmn[pos[v][i]])!=sgn(suffmn[pos[v][ptr+1]]-prefmx[pos[v][i]])) ptr++;
ans=max(ans,ptr-i+1);
}
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:88:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i=0;i<pos[v].size();i++){
| ~^~~~~~~~~~~~~~
sequence.cpp:89:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
89 | while(ptr+1<pos[v].size()&&sgn(suffmx[pos[v][ptr+1]]-prefmn[pos[v][i]])!=sgn(suffmn[pos[v][ptr+1]]-prefmx[pos[v][i]])) ptr++;
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23132 KB |
Output is correct |
2 |
Correct |
4 ms |
23188 KB |
Output is correct |
3 |
Correct |
4 ms |
23132 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23132 KB |
Output is correct |
6 |
Correct |
4 ms |
23132 KB |
Output is correct |
7 |
Correct |
5 ms |
23132 KB |
Output is correct |
8 |
Correct |
4 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
10 |
Correct |
4 ms |
23132 KB |
Output is correct |
11 |
Correct |
4 ms |
23132 KB |
Output is correct |
12 |
Correct |
4 ms |
23200 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23132 KB |
Output is correct |
2 |
Correct |
4 ms |
23188 KB |
Output is correct |
3 |
Correct |
4 ms |
23132 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23132 KB |
Output is correct |
6 |
Correct |
4 ms |
23132 KB |
Output is correct |
7 |
Correct |
5 ms |
23132 KB |
Output is correct |
8 |
Correct |
4 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
10 |
Correct |
4 ms |
23132 KB |
Output is correct |
11 |
Correct |
4 ms |
23132 KB |
Output is correct |
12 |
Correct |
4 ms |
23200 KB |
Output is correct |
13 |
Correct |
6 ms |
23176 KB |
Output is correct |
14 |
Correct |
6 ms |
23132 KB |
Output is correct |
15 |
Correct |
5 ms |
23132 KB |
Output is correct |
16 |
Correct |
5 ms |
23132 KB |
Output is correct |
17 |
Correct |
5 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
7 ms |
23132 KB |
Output is correct |
20 |
Correct |
5 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
6 ms |
23140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23132 KB |
Output is correct |
2 |
Runtime error |
100 ms |
102860 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23188 KB |
Output is correct |
2 |
Runtime error |
234 ms |
96756 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
290 ms |
123924 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23132 KB |
Output is correct |
2 |
Correct |
4 ms |
23188 KB |
Output is correct |
3 |
Correct |
4 ms |
23132 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23132 KB |
Output is correct |
6 |
Correct |
4 ms |
23132 KB |
Output is correct |
7 |
Correct |
5 ms |
23132 KB |
Output is correct |
8 |
Correct |
4 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
10 |
Correct |
4 ms |
23132 KB |
Output is correct |
11 |
Correct |
4 ms |
23132 KB |
Output is correct |
12 |
Correct |
4 ms |
23200 KB |
Output is correct |
13 |
Correct |
6 ms |
23176 KB |
Output is correct |
14 |
Correct |
6 ms |
23132 KB |
Output is correct |
15 |
Correct |
5 ms |
23132 KB |
Output is correct |
16 |
Correct |
5 ms |
23132 KB |
Output is correct |
17 |
Correct |
5 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
7 ms |
23132 KB |
Output is correct |
20 |
Correct |
5 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
6 ms |
23140 KB |
Output is correct |
23 |
Correct |
106 ms |
33128 KB |
Output is correct |
24 |
Correct |
104 ms |
33152 KB |
Output is correct |
25 |
Correct |
106 ms |
33124 KB |
Output is correct |
26 |
Correct |
96 ms |
31848 KB |
Output is correct |
27 |
Correct |
94 ms |
32060 KB |
Output is correct |
28 |
Correct |
94 ms |
32052 KB |
Output is correct |
29 |
Correct |
80 ms |
31584 KB |
Output is correct |
30 |
Correct |
79 ms |
31592 KB |
Output is correct |
31 |
Correct |
76 ms |
31944 KB |
Output is correct |
32 |
Correct |
78 ms |
33876 KB |
Output is correct |
33 |
Correct |
104 ms |
32944 KB |
Output is correct |
34 |
Correct |
113 ms |
32956 KB |
Output is correct |
35 |
Correct |
101 ms |
32848 KB |
Output is correct |
36 |
Correct |
101 ms |
32924 KB |
Output is correct |
37 |
Correct |
113 ms |
32808 KB |
Output is correct |
38 |
Correct |
101 ms |
32848 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
23132 KB |
Output is correct |
2 |
Correct |
4 ms |
23188 KB |
Output is correct |
3 |
Correct |
4 ms |
23132 KB |
Output is correct |
4 |
Correct |
4 ms |
23132 KB |
Output is correct |
5 |
Correct |
4 ms |
23132 KB |
Output is correct |
6 |
Correct |
4 ms |
23132 KB |
Output is correct |
7 |
Correct |
5 ms |
23132 KB |
Output is correct |
8 |
Correct |
4 ms |
23132 KB |
Output is correct |
9 |
Correct |
4 ms |
23132 KB |
Output is correct |
10 |
Correct |
4 ms |
23132 KB |
Output is correct |
11 |
Correct |
4 ms |
23132 KB |
Output is correct |
12 |
Correct |
4 ms |
23200 KB |
Output is correct |
13 |
Correct |
6 ms |
23176 KB |
Output is correct |
14 |
Correct |
6 ms |
23132 KB |
Output is correct |
15 |
Correct |
5 ms |
23132 KB |
Output is correct |
16 |
Correct |
5 ms |
23132 KB |
Output is correct |
17 |
Correct |
5 ms |
23132 KB |
Output is correct |
18 |
Correct |
6 ms |
23132 KB |
Output is correct |
19 |
Correct |
7 ms |
23132 KB |
Output is correct |
20 |
Correct |
5 ms |
23132 KB |
Output is correct |
21 |
Correct |
6 ms |
23132 KB |
Output is correct |
22 |
Correct |
6 ms |
23140 KB |
Output is correct |
23 |
Runtime error |
100 ms |
102860 KB |
Execution killed with signal 11 |
24 |
Halted |
0 ms |
0 KB |
- |