#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 |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35416 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35532 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 |
35420 KB |
Output is correct |
10 |
Correct |
7 ms |
35416 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 |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35416 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35532 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 |
35420 KB |
Output is correct |
10 |
Correct |
7 ms |
35416 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 |
8 ms |
35672 KB |
Output is correct |
16 |
Correct |
10 ms |
35672 KB |
Output is correct |
17 |
Correct |
9 ms |
35528 KB |
Output is correct |
18 |
Correct |
8 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35676 KB |
Output is correct |
21 |
Correct |
9 ms |
35524 KB |
Output is correct |
22 |
Correct |
9 ms |
35644 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
514 ms |
58820 KB |
Output is correct |
3 |
Correct |
525 ms |
58956 KB |
Output is correct |
4 |
Correct |
395 ms |
60772 KB |
Output is correct |
5 |
Correct |
508 ms |
59312 KB |
Output is correct |
6 |
Correct |
499 ms |
59280 KB |
Output is correct |
7 |
Correct |
405 ms |
59584 KB |
Output is correct |
8 |
Correct |
412 ms |
59976 KB |
Output is correct |
9 |
Correct |
392 ms |
62588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
409 ms |
68036 KB |
Output is correct |
3 |
Correct |
431 ms |
62792 KB |
Output is correct |
4 |
Correct |
418 ms |
62888 KB |
Output is correct |
5 |
Correct |
414 ms |
68008 KB |
Output is correct |
6 |
Correct |
412 ms |
63696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
697 ms |
57192 KB |
Output is correct |
2 |
Correct |
693 ms |
57192 KB |
Output is correct |
3 |
Correct |
764 ms |
57180 KB |
Output is correct |
4 |
Correct |
767 ms |
57188 KB |
Output is correct |
5 |
Correct |
612 ms |
57188 KB |
Output is correct |
6 |
Correct |
600 ms |
57184 KB |
Output is correct |
7 |
Correct |
487 ms |
57104 KB |
Output is correct |
8 |
Correct |
495 ms |
57316 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35416 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35532 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 |
35420 KB |
Output is correct |
10 |
Correct |
7 ms |
35416 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 |
8 ms |
35672 KB |
Output is correct |
16 |
Correct |
10 ms |
35672 KB |
Output is correct |
17 |
Correct |
9 ms |
35528 KB |
Output is correct |
18 |
Correct |
8 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35676 KB |
Output is correct |
21 |
Correct |
9 ms |
35524 KB |
Output is correct |
22 |
Correct |
9 ms |
35644 KB |
Output is correct |
23 |
Correct |
100 ms |
39380 KB |
Output is correct |
24 |
Correct |
114 ms |
39384 KB |
Output is correct |
25 |
Correct |
99 ms |
39368 KB |
Output is correct |
26 |
Correct |
85 ms |
39628 KB |
Output is correct |
27 |
Correct |
86 ms |
39624 KB |
Output is correct |
28 |
Correct |
109 ms |
39628 KB |
Output is correct |
29 |
Correct |
70 ms |
39636 KB |
Output is correct |
30 |
Correct |
78 ms |
39760 KB |
Output is correct |
31 |
Correct |
64 ms |
40456 KB |
Output is correct |
32 |
Correct |
89 ms |
39120 KB |
Output is correct |
33 |
Correct |
118 ms |
39432 KB |
Output is correct |
34 |
Correct |
109 ms |
39420 KB |
Output is correct |
35 |
Correct |
108 ms |
39652 KB |
Output is correct |
36 |
Correct |
104 ms |
39624 KB |
Output is correct |
37 |
Correct |
106 ms |
39540 KB |
Output is correct |
38 |
Correct |
109 ms |
39408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
35416 KB |
Output is correct |
2 |
Correct |
7 ms |
35416 KB |
Output is correct |
3 |
Correct |
7 ms |
35416 KB |
Output is correct |
4 |
Correct |
8 ms |
35420 KB |
Output is correct |
5 |
Correct |
7 ms |
35420 KB |
Output is correct |
6 |
Correct |
7 ms |
35532 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 |
35420 KB |
Output is correct |
10 |
Correct |
7 ms |
35416 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 |
8 ms |
35672 KB |
Output is correct |
16 |
Correct |
10 ms |
35672 KB |
Output is correct |
17 |
Correct |
9 ms |
35528 KB |
Output is correct |
18 |
Correct |
8 ms |
35676 KB |
Output is correct |
19 |
Correct |
9 ms |
35676 KB |
Output is correct |
20 |
Correct |
9 ms |
35676 KB |
Output is correct |
21 |
Correct |
9 ms |
35524 KB |
Output is correct |
22 |
Correct |
9 ms |
35644 KB |
Output is correct |
23 |
Correct |
514 ms |
58820 KB |
Output is correct |
24 |
Correct |
525 ms |
58956 KB |
Output is correct |
25 |
Correct |
395 ms |
60772 KB |
Output is correct |
26 |
Correct |
508 ms |
59312 KB |
Output is correct |
27 |
Correct |
499 ms |
59280 KB |
Output is correct |
28 |
Correct |
405 ms |
59584 KB |
Output is correct |
29 |
Correct |
412 ms |
59976 KB |
Output is correct |
30 |
Correct |
392 ms |
62588 KB |
Output is correct |
31 |
Correct |
409 ms |
68036 KB |
Output is correct |
32 |
Correct |
431 ms |
62792 KB |
Output is correct |
33 |
Correct |
418 ms |
62888 KB |
Output is correct |
34 |
Correct |
414 ms |
68008 KB |
Output is correct |
35 |
Correct |
412 ms |
63696 KB |
Output is correct |
36 |
Correct |
697 ms |
57192 KB |
Output is correct |
37 |
Correct |
693 ms |
57192 KB |
Output is correct |
38 |
Correct |
764 ms |
57180 KB |
Output is correct |
39 |
Correct |
767 ms |
57188 KB |
Output is correct |
40 |
Correct |
612 ms |
57188 KB |
Output is correct |
41 |
Correct |
600 ms |
57184 KB |
Output is correct |
42 |
Correct |
487 ms |
57104 KB |
Output is correct |
43 |
Correct |
495 ms |
57316 KB |
Output is correct |
44 |
Correct |
100 ms |
39380 KB |
Output is correct |
45 |
Correct |
114 ms |
39384 KB |
Output is correct |
46 |
Correct |
99 ms |
39368 KB |
Output is correct |
47 |
Correct |
85 ms |
39628 KB |
Output is correct |
48 |
Correct |
86 ms |
39624 KB |
Output is correct |
49 |
Correct |
109 ms |
39628 KB |
Output is correct |
50 |
Correct |
70 ms |
39636 KB |
Output is correct |
51 |
Correct |
78 ms |
39760 KB |
Output is correct |
52 |
Correct |
64 ms |
40456 KB |
Output is correct |
53 |
Correct |
89 ms |
39120 KB |
Output is correct |
54 |
Correct |
118 ms |
39432 KB |
Output is correct |
55 |
Correct |
109 ms |
39420 KB |
Output is correct |
56 |
Correct |
108 ms |
39652 KB |
Output is correct |
57 |
Correct |
104 ms |
39624 KB |
Output is correct |
58 |
Correct |
106 ms |
39540 KB |
Output is correct |
59 |
Correct |
109 ms |
39408 KB |
Output is correct |
60 |
Correct |
934 ms |
58948 KB |
Output is correct |
61 |
Correct |
863 ms |
59072 KB |
Output is correct |
62 |
Correct |
851 ms |
59072 KB |
Output is correct |
63 |
Correct |
617 ms |
60352 KB |
Output is correct |
64 |
Correct |
556 ms |
60340 KB |
Output is correct |
65 |
Correct |
628 ms |
60352 KB |
Output is correct |
66 |
Correct |
443 ms |
61628 KB |
Output is correct |
67 |
Correct |
436 ms |
61888 KB |
Output is correct |
68 |
Correct |
393 ms |
65200 KB |
Output is correct |
69 |
Correct |
508 ms |
57188 KB |
Output is correct |
70 |
Correct |
795 ms |
60004 KB |
Output is correct |
71 |
Correct |
830 ms |
60352 KB |
Output is correct |
72 |
Correct |
774 ms |
60676 KB |
Output is correct |
73 |
Correct |
765 ms |
60396 KB |
Output is correct |
74 |
Correct |
744 ms |
60812 KB |
Output is correct |
75 |
Correct |
766 ms |
60424 KB |
Output is correct |