#include "sequence.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int const n_max=5e5+10;
struct Node{
int sum;
int mn;
int mx;
Node():sum(0),mn(0),mx(0){}
Node(int a):sum(a),mn(min(0,a)),mx(max(0,a)){}
Node operator +(Node a)
{
Node ret;
ret.sum=sum+a.sum;
ret.mn=min(mn,sum+a.mn);
ret.mx=max(mx,sum+a.mx);
return ret;
}
};
Node tree[4*n_max];
void upd(int idx,int l,int r,int p,int v)
{
if(p<l||r<p)return;
if(l==r)
{
tree[idx]=Node(v);
return;
}
int mid=(l+r)>>1;
if(p<=mid)upd(idx<<1,l,mid,p,v);
else upd(idx<<1^1,mid+1,r,p,v);
tree[idx]=tree[idx<<1]+tree[idx<<1^1];
}
Node qr(int idx,int l,int r,int ll,int rr)
{
if(rr<l||r<ll)return Node();
if(ll<=l&&r<=rr)return tree[idx];
int mid=(l+r)>>1;
return qr(idx<<1,l,mid,ll,rr)+qr(idx<<1^1,mid+1,r,ll,rr);
}
vector<int> A;
vector<int> pos[n_max];
int sequence(int N, vector<int> _A)
{
A.push_back(0);
for(int i=0;i<N;i++)A.push_back(_A[i]);
for(int i=1;i<=N;i++)pos[i].push_back(0);
for(int i=1;i<=N;i++)pos[A[i]].push_back(i),upd(1,1,N,i,1);
for(int i=1;i<=N;i++)pos[i].push_back(N+1);
int ans=1;
for(int i=1;i<=N;i++)
{
for(auto it:pos[i])upd(1,1,N,it,0);
for(auto it:pos[i-1])upd(1,1,N,it,-1);
vector<pii> keep;
int time=0;
for(int j=1;j<pos[i].size();j++)
{
Node temp=qr(1,1,N,pos[i][j-1]+1,pos[i][j]-1);
keep.push_back({time+temp.mn,time+temp.mx});
time+=temp.sum;
}
for(int j=1;j<keep.size();j++)
{
int l=0,r=j;
while(l<r)
{
int mid=(l+r)>>1;
if(-(j-mid)>keep[j].se-keep[mid].fi||keep[j].fi-keep[mid].se>j-mid)l=mid+1;
else r=mid;
}
ans=max(ans,j-l);
keep[j]={min(keep[j].fi,keep[j-1].fi),max(keep[j].se,keep[j-1].se)};
}
}
return ans;
}
Compilation message
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int j=1;j<pos[i].size();j++)
| ~^~~~~~~~~~~~~~
sequence.cpp:67:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int j=1;j<keep.size();j++)
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Incorrect |
9 ms |
35544 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Incorrect |
9 ms |
35544 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
35416 KB |
Output is correct |
2 |
Correct |
515 ms |
58944 KB |
Output is correct |
3 |
Correct |
522 ms |
58720 KB |
Output is correct |
4 |
Correct |
391 ms |
60984 KB |
Output is correct |
5 |
Correct |
541 ms |
59308 KB |
Output is correct |
6 |
Correct |
541 ms |
59280 KB |
Output is correct |
7 |
Correct |
425 ms |
59824 KB |
Output is correct |
8 |
Correct |
436 ms |
59972 KB |
Output is correct |
9 |
Correct |
412 ms |
62568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35420 KB |
Output is correct |
2 |
Correct |
444 ms |
66360 KB |
Output is correct |
3 |
Correct |
420 ms |
62884 KB |
Output is correct |
4 |
Correct |
429 ms |
62888 KB |
Output is correct |
5 |
Correct |
419 ms |
67748 KB |
Output is correct |
6 |
Correct |
408 ms |
63516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
742 ms |
57192 KB |
Output is correct |
2 |
Correct |
726 ms |
57184 KB |
Output is correct |
3 |
Correct |
750 ms |
57196 KB |
Output is correct |
4 |
Correct |
719 ms |
57284 KB |
Output is correct |
5 |
Correct |
590 ms |
57024 KB |
Output is correct |
6 |
Correct |
611 ms |
57188 KB |
Output is correct |
7 |
Correct |
498 ms |
57196 KB |
Output is correct |
8 |
Correct |
486 ms |
57192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Incorrect |
9 ms |
35544 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Incorrect |
9 ms |
35544 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |