#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]) prefmx[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]) prefmn[i]=query(1,0,n,0,i-1).fi,suffmn[i]=query(1,0,n,i,n).se;
if(v==1){
for(int i:pos[v]) printf("%d %d\n",prefmx[i],suffmx[i]);
printf("-\n");
for(int i:pos[v]) printf("%d %d\n",prefmn[i],suffmn[i]);
}
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:93:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
93 | for(int i=0;i<pos[v].size();i++){
| ~^~~~~~~~~~~~~~
sequence.cpp:94:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
94 | 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 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
330 ms |
127284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
23132 KB |
secret mismatch |
| 2 |
Halted |
0 ms |
0 KB |
- |
