#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>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].fi+=j;
keep[j].se-=j;
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 |
8 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
8 ms |
35416 KB |
Output is correct |
6 |
Correct |
7 ms |
35416 KB |
Output is correct |
7 |
Correct |
7 ms |
35420 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35416 KB |
Output is correct |
10 |
Correct |
7 ms |
35640 KB |
Output is correct |
11 |
Correct |
7 ms |
35420 KB |
Output is correct |
12 |
Correct |
7 ms |
35420 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
8 ms |
35416 KB |
Output is correct |
6 |
Correct |
7 ms |
35416 KB |
Output is correct |
7 |
Correct |
7 ms |
35420 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35416 KB |
Output is correct |
10 |
Correct |
7 ms |
35640 KB |
Output is correct |
11 |
Correct |
7 ms |
35420 KB |
Output is correct |
12 |
Correct |
7 ms |
35420 KB |
Output is correct |
13 |
Correct |
9 ms |
35676 KB |
Output is correct |
14 |
Correct |
9 ms |
35676 KB |
Output is correct |
15 |
Correct |
9 ms |
35676 KB |
Output is correct |
16 |
Correct |
9 ms |
35676 KB |
Output is correct |
17 |
Correct |
11 ms |
35676 KB |
Output is correct |
18 |
Correct |
9 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35656 KB |
Output is correct |
21 |
Correct |
9 ms |
35676 KB |
Output is correct |
22 |
Correct |
9 ms |
35648 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
35416 KB |
Output is correct |
2 |
Correct |
503 ms |
58936 KB |
Output is correct |
3 |
Correct |
518 ms |
58956 KB |
Output is correct |
4 |
Correct |
400 ms |
61120 KB |
Output is correct |
5 |
Correct |
514 ms |
59240 KB |
Output is correct |
6 |
Correct |
503 ms |
59224 KB |
Output is correct |
7 |
Correct |
403 ms |
59844 KB |
Output is correct |
8 |
Correct |
394 ms |
59844 KB |
Output is correct |
9 |
Correct |
414 ms |
63544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
420 ms |
66880 KB |
Output is correct |
3 |
Correct |
442 ms |
62868 KB |
Output is correct |
4 |
Correct |
429 ms |
62904 KB |
Output is correct |
5 |
Correct |
421 ms |
67748 KB |
Output is correct |
6 |
Correct |
417 ms |
63644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
779 ms |
57184 KB |
Output is correct |
2 |
Correct |
709 ms |
57204 KB |
Output is correct |
3 |
Correct |
691 ms |
57028 KB |
Output is correct |
4 |
Correct |
704 ms |
57176 KB |
Output is correct |
5 |
Correct |
604 ms |
57192 KB |
Output is correct |
6 |
Correct |
598 ms |
57188 KB |
Output is correct |
7 |
Correct |
492 ms |
57192 KB |
Output is correct |
8 |
Correct |
518 ms |
57188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
8 ms |
35416 KB |
Output is correct |
6 |
Correct |
7 ms |
35416 KB |
Output is correct |
7 |
Correct |
7 ms |
35420 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35416 KB |
Output is correct |
10 |
Correct |
7 ms |
35640 KB |
Output is correct |
11 |
Correct |
7 ms |
35420 KB |
Output is correct |
12 |
Correct |
7 ms |
35420 KB |
Output is correct |
13 |
Correct |
9 ms |
35676 KB |
Output is correct |
14 |
Correct |
9 ms |
35676 KB |
Output is correct |
15 |
Correct |
9 ms |
35676 KB |
Output is correct |
16 |
Correct |
9 ms |
35676 KB |
Output is correct |
17 |
Correct |
11 ms |
35676 KB |
Output is correct |
18 |
Correct |
9 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35656 KB |
Output is correct |
21 |
Correct |
9 ms |
35676 KB |
Output is correct |
22 |
Correct |
9 ms |
35648 KB |
Output is correct |
23 |
Correct |
100 ms |
39848 KB |
Output is correct |
24 |
Correct |
105 ms |
39844 KB |
Output is correct |
25 |
Correct |
121 ms |
39624 KB |
Output is correct |
26 |
Correct |
83 ms |
40060 KB |
Output is correct |
27 |
Correct |
83 ms |
39892 KB |
Output is correct |
28 |
Correct |
91 ms |
40140 KB |
Output is correct |
29 |
Correct |
72 ms |
39624 KB |
Output is correct |
30 |
Correct |
71 ms |
39744 KB |
Output is correct |
31 |
Correct |
65 ms |
40912 KB |
Output is correct |
32 |
Correct |
77 ms |
39380 KB |
Output is correct |
33 |
Correct |
98 ms |
39884 KB |
Output is correct |
34 |
Correct |
111 ms |
39868 KB |
Output is correct |
35 |
Correct |
95 ms |
40116 KB |
Output is correct |
36 |
Correct |
110 ms |
40112 KB |
Output is correct |
37 |
Correct |
99 ms |
39896 KB |
Output is correct |
38 |
Correct |
103 ms |
39868 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35420 KB |
Output is correct |
4 |
Correct |
7 ms |
35420 KB |
Output is correct |
5 |
Correct |
8 ms |
35416 KB |
Output is correct |
6 |
Correct |
7 ms |
35416 KB |
Output is correct |
7 |
Correct |
7 ms |
35420 KB |
Output is correct |
8 |
Correct |
7 ms |
35420 KB |
Output is correct |
9 |
Correct |
7 ms |
35416 KB |
Output is correct |
10 |
Correct |
7 ms |
35640 KB |
Output is correct |
11 |
Correct |
7 ms |
35420 KB |
Output is correct |
12 |
Correct |
7 ms |
35420 KB |
Output is correct |
13 |
Correct |
9 ms |
35676 KB |
Output is correct |
14 |
Correct |
9 ms |
35676 KB |
Output is correct |
15 |
Correct |
9 ms |
35676 KB |
Output is correct |
16 |
Correct |
9 ms |
35676 KB |
Output is correct |
17 |
Correct |
11 ms |
35676 KB |
Output is correct |
18 |
Correct |
9 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35656 KB |
Output is correct |
21 |
Correct |
9 ms |
35676 KB |
Output is correct |
22 |
Correct |
9 ms |
35648 KB |
Output is correct |
23 |
Correct |
503 ms |
58936 KB |
Output is correct |
24 |
Correct |
518 ms |
58956 KB |
Output is correct |
25 |
Correct |
400 ms |
61120 KB |
Output is correct |
26 |
Correct |
514 ms |
59240 KB |
Output is correct |
27 |
Correct |
503 ms |
59224 KB |
Output is correct |
28 |
Correct |
403 ms |
59844 KB |
Output is correct |
29 |
Correct |
394 ms |
59844 KB |
Output is correct |
30 |
Correct |
414 ms |
63544 KB |
Output is correct |
31 |
Correct |
420 ms |
66880 KB |
Output is correct |
32 |
Correct |
442 ms |
62868 KB |
Output is correct |
33 |
Correct |
429 ms |
62904 KB |
Output is correct |
34 |
Correct |
421 ms |
67748 KB |
Output is correct |
35 |
Correct |
417 ms |
63644 KB |
Output is correct |
36 |
Correct |
779 ms |
57184 KB |
Output is correct |
37 |
Correct |
709 ms |
57204 KB |
Output is correct |
38 |
Correct |
691 ms |
57028 KB |
Output is correct |
39 |
Correct |
704 ms |
57176 KB |
Output is correct |
40 |
Correct |
604 ms |
57192 KB |
Output is correct |
41 |
Correct |
598 ms |
57188 KB |
Output is correct |
42 |
Correct |
492 ms |
57192 KB |
Output is correct |
43 |
Correct |
518 ms |
57188 KB |
Output is correct |
44 |
Correct |
100 ms |
39848 KB |
Output is correct |
45 |
Correct |
105 ms |
39844 KB |
Output is correct |
46 |
Correct |
121 ms |
39624 KB |
Output is correct |
47 |
Correct |
83 ms |
40060 KB |
Output is correct |
48 |
Correct |
83 ms |
39892 KB |
Output is correct |
49 |
Correct |
91 ms |
40140 KB |
Output is correct |
50 |
Correct |
72 ms |
39624 KB |
Output is correct |
51 |
Correct |
71 ms |
39744 KB |
Output is correct |
52 |
Correct |
65 ms |
40912 KB |
Output is correct |
53 |
Correct |
77 ms |
39380 KB |
Output is correct |
54 |
Correct |
98 ms |
39884 KB |
Output is correct |
55 |
Correct |
111 ms |
39868 KB |
Output is correct |
56 |
Correct |
95 ms |
40116 KB |
Output is correct |
57 |
Correct |
110 ms |
40112 KB |
Output is correct |
58 |
Correct |
99 ms |
39896 KB |
Output is correct |
59 |
Correct |
103 ms |
39868 KB |
Output is correct |
60 |
Correct |
828 ms |
62256 KB |
Output is correct |
61 |
Correct |
832 ms |
62552 KB |
Output is correct |
62 |
Correct |
891 ms |
62256 KB |
Output is correct |
63 |
Correct |
597 ms |
62228 KB |
Output is correct |
64 |
Correct |
619 ms |
62216 KB |
Output is correct |
65 |
Correct |
608 ms |
62404 KB |
Output is correct |
66 |
Correct |
424 ms |
62404 KB |
Output is correct |
67 |
Correct |
434 ms |
62692 KB |
Output is correct |
68 |
Correct |
435 ms |
68292 KB |
Output is correct |
69 |
Correct |
559 ms |
60504 KB |
Output is correct |
70 |
Correct |
856 ms |
63264 KB |
Output is correct |
71 |
Correct |
867 ms |
63840 KB |
Output is correct |
72 |
Correct |
797 ms |
63936 KB |
Output is correct |
73 |
Correct |
852 ms |
63768 KB |
Output is correct |
74 |
Correct |
815 ms |
64100 KB |
Output is correct |
75 |
Correct |
831 ms |
63892 KB |
Output is correct |