#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=0;
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>keep[j].se-keep[mid].fi||keep[j].fi-keep[mid].se>j)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++)
| ~^~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
35416 KB |
Output is correct |
2 |
Correct |
8 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35420 KB |
Output is correct |
7 |
Correct |
7 ms |
35416 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35528 KB |
Output is correct |
10 |
Correct |
7 ms |
35544 KB |
Output is correct |
11 |
Incorrect |
8 ms |
35420 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
35416 KB |
Output is correct |
2 |
Correct |
8 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35420 KB |
Output is correct |
7 |
Correct |
7 ms |
35416 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35528 KB |
Output is correct |
10 |
Correct |
7 ms |
35544 KB |
Output is correct |
11 |
Incorrect |
8 ms |
35420 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
35416 KB |
Output is correct |
2 |
Correct |
535 ms |
58940 KB |
Output is correct |
3 |
Correct |
525 ms |
62268 KB |
Output is correct |
4 |
Correct |
398 ms |
61972 KB |
Output is correct |
5 |
Correct |
505 ms |
62404 KB |
Output is correct |
6 |
Correct |
503 ms |
62528 KB |
Output is correct |
7 |
Correct |
398 ms |
61216 KB |
Output is correct |
8 |
Correct |
391 ms |
61120 KB |
Output is correct |
9 |
Correct |
395 ms |
63444 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
35420 KB |
Output is correct |
2 |
Correct |
407 ms |
67032 KB |
Output is correct |
3 |
Correct |
449 ms |
63988 KB |
Output is correct |
4 |
Correct |
423 ms |
63680 KB |
Output is correct |
5 |
Correct |
461 ms |
67932 KB |
Output is correct |
6 |
Incorrect |
416 ms |
64428 KB |
Output isn't correct |
7 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
758 ms |
57192 KB |
Output is correct |
2 |
Correct |
746 ms |
60440 KB |
Output is correct |
3 |
Correct |
793 ms |
60472 KB |
Output is correct |
4 |
Correct |
741 ms |
60476 KB |
Output is correct |
5 |
Correct |
613 ms |
60392 KB |
Output is correct |
6 |
Correct |
636 ms |
60388 KB |
Output is correct |
7 |
Correct |
488 ms |
60352 KB |
Output is correct |
8 |
Correct |
490 ms |
60420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
35416 KB |
Output is correct |
2 |
Correct |
8 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35420 KB |
Output is correct |
7 |
Correct |
7 ms |
35416 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35528 KB |
Output is correct |
10 |
Correct |
7 ms |
35544 KB |
Output is correct |
11 |
Incorrect |
8 ms |
35420 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
35416 KB |
Output is correct |
2 |
Correct |
8 ms |
35420 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35420 KB |
Output is correct |
7 |
Correct |
7 ms |
35416 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35528 KB |
Output is correct |
10 |
Correct |
7 ms |
35544 KB |
Output is correct |
11 |
Incorrect |
8 ms |
35420 KB |
Output isn't correct |
12 |
Halted |
0 ms |
0 KB |
- |