#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 5e5;
int N, A[MAXN+10];
vector<int> V[MAXN+10];
struct Node
{
int sum, minv, maxv;
Node() : sum(0), minv(0), maxv(0) {}
Node(int x) : sum(x), minv(min(x, 0)), maxv(max(x, 0)) {}
};
Node operator + (const Node &p, const Node &q)
{
Node ret;
ret.sum=p.sum+q.sum;
ret.minv=min(p.minv, p.sum+q.minv);
ret.maxv=max(p.maxv, p.sum+q.maxv);
return ret;
}
struct SEG
{
Node tree[MAXN*4+10];
void update(int node, int tl, int tr, int p, int q)
{
if(p<tl || tr<p) return;
if(tl==tr)
{
tree[node]=Node(q);
return;
}
int mid=tl+tr>>1;
if(p<=mid) update(node*2, tl, mid, p, q);
else update(node*2+1, mid+1, tr, p, q);
tree[node]=tree[node*2]+tree[node*2+1];
}
Node query(int node, int tl, int tr, int l, int r)
{
if(l<=tl && tr<=r) return tree[node];
if(r<tl || tr<l) return Node();
int mid=tl+tr>>1;
return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r);
}
}seg;
int sequence(int _N, std::vector<int> _A)
{
N=_N;
for(int i=1; i<=N; i++) A[i]=_A[i-1];
for(int i=1; i<=N; i++) V[i].push_back(0);
for(int i=1; i<=N; i++) V[A[i]].push_back(i);
for(int i=1; i<=N; i++) V[i].push_back(N+1);
for(int i=1; i<=N; i++) seg.update(1, 1, N, i, 1);
int ans=0;
for(int i=1; i<=N; i++)
{
for(auto it : V[i]) seg.update(1, 1, N, it, 0);
for(auto it : V[i-1]) seg.update(1, 1, N, it, -1);
vector<pii> VV;
int t=0;
for(int j=1; j<V[i].size(); j++)
{
Node nd=seg.query(1, 1, N, V[i][j-1]+1, V[i][j]-1);
VV.push_back({t+nd.minv, t+nd.maxv});
t+=nd.sum;
}
//for(auto it : VV) printf("%d %d\n", it.first, it.second);
for(int j=0; j<VV.size(); j++)
{
int lo=-1, hi=j;
while(lo+1<hi)
{
int mid=lo+hi>>1;
if(VV[j].second+j<VV[mid].first || VV[j].first-j>VV[mid].second) lo=mid;
else hi=mid;
}
ans=max(ans, j-hi);
VV[j].first+=j; VV[j].second-=j;
if(j)
{
VV[j].first=min(VV[j].first, VV[j-1].first);
VV[j].second=max(VV[j].second, VV[j-1].second);
}
}
//printf("-> %d\n", i);
}
return ans;
}
Compilation message
sequence.cpp: In member function 'void SEG::update(int, int, int, int, int)':
sequence.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int mid=tl+tr>>1;
| ~~^~~
sequence.cpp: In member function 'Node SEG::query(int, int, int, int, int)':
sequence.cpp:51:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
51 | int mid=tl+tr>>1;
| ~~^~~
sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int j=1; j<V[i].size(); j++)
| ~^~~~~~~~~~~~
sequence.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int j=0; j<VV.size(); j++)
| ~^~~~~~~~~~
sequence.cpp:85:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
85 | int mid=lo+hi>>1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
35412 KB |
Output is correct |
2 |
Correct |
17 ms |
35508 KB |
Output is correct |
3 |
Correct |
17 ms |
35504 KB |
Output is correct |
4 |
Correct |
17 ms |
35540 KB |
Output is correct |
5 |
Correct |
16 ms |
35540 KB |
Output is correct |
6 |
Correct |
15 ms |
35476 KB |
Output is correct |
7 |
Correct |
22 ms |
35540 KB |
Output is correct |
8 |
Correct |
20 ms |
35528 KB |
Output is correct |
9 |
Correct |
16 ms |
35432 KB |
Output is correct |
10 |
Correct |
15 ms |
35436 KB |
Output is correct |
11 |
Correct |
16 ms |
35540 KB |
Output is correct |
12 |
Correct |
15 ms |
35524 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
35412 KB |
Output is correct |
2 |
Correct |
17 ms |
35508 KB |
Output is correct |
3 |
Correct |
17 ms |
35504 KB |
Output is correct |
4 |
Correct |
17 ms |
35540 KB |
Output is correct |
5 |
Correct |
16 ms |
35540 KB |
Output is correct |
6 |
Correct |
15 ms |
35476 KB |
Output is correct |
7 |
Correct |
22 ms |
35540 KB |
Output is correct |
8 |
Correct |
20 ms |
35528 KB |
Output is correct |
9 |
Correct |
16 ms |
35432 KB |
Output is correct |
10 |
Correct |
15 ms |
35436 KB |
Output is correct |
11 |
Correct |
16 ms |
35540 KB |
Output is correct |
12 |
Correct |
15 ms |
35524 KB |
Output is correct |
13 |
Correct |
18 ms |
35616 KB |
Output is correct |
14 |
Correct |
23 ms |
35588 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
23 ms |
35620 KB |
Output is correct |
17 |
Correct |
18 ms |
35540 KB |
Output is correct |
18 |
Correct |
19 ms |
35620 KB |
Output is correct |
19 |
Correct |
25 ms |
35512 KB |
Output is correct |
20 |
Correct |
26 ms |
35540 KB |
Output is correct |
21 |
Correct |
20 ms |
35636 KB |
Output is correct |
22 |
Correct |
19 ms |
35548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
35412 KB |
Output is correct |
2 |
Correct |
521 ms |
58804 KB |
Output is correct |
3 |
Correct |
540 ms |
58808 KB |
Output is correct |
4 |
Correct |
425 ms |
60840 KB |
Output is correct |
5 |
Correct |
514 ms |
59176 KB |
Output is correct |
6 |
Correct |
496 ms |
59084 KB |
Output is correct |
7 |
Correct |
400 ms |
59676 KB |
Output is correct |
8 |
Correct |
417 ms |
59828 KB |
Output is correct |
9 |
Correct |
403 ms |
62244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
35508 KB |
Output is correct |
2 |
Correct |
437 ms |
65092 KB |
Output is correct |
3 |
Correct |
435 ms |
62332 KB |
Output is correct |
4 |
Correct |
398 ms |
62352 KB |
Output is correct |
5 |
Correct |
401 ms |
65292 KB |
Output is correct |
6 |
Correct |
384 ms |
62904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
704 ms |
57048 KB |
Output is correct |
2 |
Correct |
720 ms |
57048 KB |
Output is correct |
3 |
Correct |
682 ms |
56920 KB |
Output is correct |
4 |
Correct |
709 ms |
57080 KB |
Output is correct |
5 |
Correct |
578 ms |
57048 KB |
Output is correct |
6 |
Correct |
614 ms |
57052 KB |
Output is correct |
7 |
Correct |
511 ms |
57048 KB |
Output is correct |
8 |
Correct |
440 ms |
57048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
35412 KB |
Output is correct |
2 |
Correct |
17 ms |
35508 KB |
Output is correct |
3 |
Correct |
17 ms |
35504 KB |
Output is correct |
4 |
Correct |
17 ms |
35540 KB |
Output is correct |
5 |
Correct |
16 ms |
35540 KB |
Output is correct |
6 |
Correct |
15 ms |
35476 KB |
Output is correct |
7 |
Correct |
22 ms |
35540 KB |
Output is correct |
8 |
Correct |
20 ms |
35528 KB |
Output is correct |
9 |
Correct |
16 ms |
35432 KB |
Output is correct |
10 |
Correct |
15 ms |
35436 KB |
Output is correct |
11 |
Correct |
16 ms |
35540 KB |
Output is correct |
12 |
Correct |
15 ms |
35524 KB |
Output is correct |
13 |
Correct |
18 ms |
35616 KB |
Output is correct |
14 |
Correct |
23 ms |
35588 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
23 ms |
35620 KB |
Output is correct |
17 |
Correct |
18 ms |
35540 KB |
Output is correct |
18 |
Correct |
19 ms |
35620 KB |
Output is correct |
19 |
Correct |
25 ms |
35512 KB |
Output is correct |
20 |
Correct |
26 ms |
35540 KB |
Output is correct |
21 |
Correct |
20 ms |
35636 KB |
Output is correct |
22 |
Correct |
19 ms |
35548 KB |
Output is correct |
23 |
Correct |
146 ms |
39244 KB |
Output is correct |
24 |
Correct |
120 ms |
39264 KB |
Output is correct |
25 |
Correct |
112 ms |
39268 KB |
Output is correct |
26 |
Correct |
96 ms |
39636 KB |
Output is correct |
27 |
Correct |
91 ms |
39636 KB |
Output is correct |
28 |
Correct |
93 ms |
39628 KB |
Output is correct |
29 |
Correct |
80 ms |
39632 KB |
Output is correct |
30 |
Correct |
78 ms |
39620 KB |
Output is correct |
31 |
Correct |
85 ms |
40460 KB |
Output is correct |
32 |
Correct |
83 ms |
38912 KB |
Output is correct |
33 |
Correct |
113 ms |
39432 KB |
Output is correct |
34 |
Correct |
116 ms |
39528 KB |
Output is correct |
35 |
Correct |
119 ms |
39444 KB |
Output is correct |
36 |
Correct |
111 ms |
39420 KB |
Output is correct |
37 |
Correct |
107 ms |
39452 KB |
Output is correct |
38 |
Correct |
118 ms |
39472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
23 ms |
35412 KB |
Output is correct |
2 |
Correct |
17 ms |
35508 KB |
Output is correct |
3 |
Correct |
17 ms |
35504 KB |
Output is correct |
4 |
Correct |
17 ms |
35540 KB |
Output is correct |
5 |
Correct |
16 ms |
35540 KB |
Output is correct |
6 |
Correct |
15 ms |
35476 KB |
Output is correct |
7 |
Correct |
22 ms |
35540 KB |
Output is correct |
8 |
Correct |
20 ms |
35528 KB |
Output is correct |
9 |
Correct |
16 ms |
35432 KB |
Output is correct |
10 |
Correct |
15 ms |
35436 KB |
Output is correct |
11 |
Correct |
16 ms |
35540 KB |
Output is correct |
12 |
Correct |
15 ms |
35524 KB |
Output is correct |
13 |
Correct |
18 ms |
35616 KB |
Output is correct |
14 |
Correct |
23 ms |
35588 KB |
Output is correct |
15 |
Correct |
18 ms |
35540 KB |
Output is correct |
16 |
Correct |
23 ms |
35620 KB |
Output is correct |
17 |
Correct |
18 ms |
35540 KB |
Output is correct |
18 |
Correct |
19 ms |
35620 KB |
Output is correct |
19 |
Correct |
25 ms |
35512 KB |
Output is correct |
20 |
Correct |
26 ms |
35540 KB |
Output is correct |
21 |
Correct |
20 ms |
35636 KB |
Output is correct |
22 |
Correct |
19 ms |
35548 KB |
Output is correct |
23 |
Correct |
521 ms |
58804 KB |
Output is correct |
24 |
Correct |
540 ms |
58808 KB |
Output is correct |
25 |
Correct |
425 ms |
60840 KB |
Output is correct |
26 |
Correct |
514 ms |
59176 KB |
Output is correct |
27 |
Correct |
496 ms |
59084 KB |
Output is correct |
28 |
Correct |
400 ms |
59676 KB |
Output is correct |
29 |
Correct |
417 ms |
59828 KB |
Output is correct |
30 |
Correct |
403 ms |
62244 KB |
Output is correct |
31 |
Correct |
437 ms |
65092 KB |
Output is correct |
32 |
Correct |
435 ms |
62332 KB |
Output is correct |
33 |
Correct |
398 ms |
62352 KB |
Output is correct |
34 |
Correct |
401 ms |
65292 KB |
Output is correct |
35 |
Correct |
384 ms |
62904 KB |
Output is correct |
36 |
Correct |
704 ms |
57048 KB |
Output is correct |
37 |
Correct |
720 ms |
57048 KB |
Output is correct |
38 |
Correct |
682 ms |
56920 KB |
Output is correct |
39 |
Correct |
709 ms |
57080 KB |
Output is correct |
40 |
Correct |
578 ms |
57048 KB |
Output is correct |
41 |
Correct |
614 ms |
57052 KB |
Output is correct |
42 |
Correct |
511 ms |
57048 KB |
Output is correct |
43 |
Correct |
440 ms |
57048 KB |
Output is correct |
44 |
Correct |
146 ms |
39244 KB |
Output is correct |
45 |
Correct |
120 ms |
39264 KB |
Output is correct |
46 |
Correct |
112 ms |
39268 KB |
Output is correct |
47 |
Correct |
96 ms |
39636 KB |
Output is correct |
48 |
Correct |
91 ms |
39636 KB |
Output is correct |
49 |
Correct |
93 ms |
39628 KB |
Output is correct |
50 |
Correct |
80 ms |
39632 KB |
Output is correct |
51 |
Correct |
78 ms |
39620 KB |
Output is correct |
52 |
Correct |
85 ms |
40460 KB |
Output is correct |
53 |
Correct |
83 ms |
38912 KB |
Output is correct |
54 |
Correct |
113 ms |
39432 KB |
Output is correct |
55 |
Correct |
116 ms |
39528 KB |
Output is correct |
56 |
Correct |
119 ms |
39444 KB |
Output is correct |
57 |
Correct |
111 ms |
39420 KB |
Output is correct |
58 |
Correct |
107 ms |
39452 KB |
Output is correct |
59 |
Correct |
118 ms |
39472 KB |
Output is correct |
60 |
Correct |
852 ms |
58796 KB |
Output is correct |
61 |
Correct |
825 ms |
58864 KB |
Output is correct |
62 |
Correct |
831 ms |
58868 KB |
Output is correct |
63 |
Correct |
568 ms |
60228 KB |
Output is correct |
64 |
Correct |
602 ms |
60144 KB |
Output is correct |
65 |
Correct |
570 ms |
60240 KB |
Output is correct |
66 |
Correct |
398 ms |
60844 KB |
Output is correct |
67 |
Correct |
430 ms |
60848 KB |
Output is correct |
68 |
Correct |
385 ms |
63240 KB |
Output is correct |
69 |
Correct |
472 ms |
56956 KB |
Output is correct |
70 |
Correct |
787 ms |
59512 KB |
Output is correct |
71 |
Correct |
803 ms |
60020 KB |
Output is correct |
72 |
Correct |
748 ms |
60144 KB |
Output is correct |
73 |
Correct |
749 ms |
60008 KB |
Output is correct |
74 |
Correct |
745 ms |
60416 KB |
Output is correct |
75 |
Correct |
759 ms |
60076 KB |
Output is correct |