#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5, INF=1e9;
int n;
struct node{
int mn, mx;
node(int mn=0, int mx=0) : mn(mn), mx(mx) {}
};
node pull(node L, node R) {
int MN, MX;
MN=min(L.mn, R.mn);
MX=max(L.mx, R.mx);
return node(MN, MX);
}
struct ST{
node tr[4*N];
int lazy[4*N];
node build(int pos=0, int l=0, int r=n) {
lazy[pos]=0;
if(l==r) return tr[pos]=node(l, r);
int mid=l+r>>1;
return tr[pos]=pull(build(2*pos+1, l, mid), build(2*pos+2, mid+1, r));
}
void change(int pos, int add) {
tr[pos].mn+=add;
tr[pos].mx+=add;
lazy[pos]+=add;
}
void push(int pos) {
change(2*pos+1, lazy[pos]);
change(2*pos+2, lazy[pos]);
lazy[pos]=0;
}
void update(int ll, int rr, int add, int pos=0, int l=0, int r=n) {
if(ll>rr) return;
if(ll==l && rr==r) {change(pos, add); return;}
push(pos); int mid=l+r>>1;
update(ll, min(rr, mid), add, 2*pos+1, l, mid);
update(max(mid+1, ll), rr, add, 2*pos+2, mid+1, r);
tr[pos]=pull(tr[2*pos+1], tr[2*pos+2]);
}
node get(int ll, int rr, int pos=0, int l=0, int r=n) {
if(ll>rr) return node(INF, -INF);
if(ll==l && rr==r) return tr[pos];
push(pos);int mid=l+r>>1;
return pull(get(ll, min(rr, mid), 2*pos+1, l, mid), get(max(mid+1, ll), rr, 2*pos+2, mid+1, r));
}
} nega, posi;
int sequence(int N, vector<int> a) {
n=N;
vector<vector<int>> pos(n+1);
nega.build();
posi.build();
for(int i=0; i<n; i++) pos[a[i]].push_back(i+1);
int ans=1;
for(int val=1; val<=n; val++) {
int SZ=pos[val].size();
for(int p : pos[val]) nega.update(p, n, -2);
for(int p : pos[val-1]) posi.update(p, n, -2);
for(int i=0; i<SZ; i++) {
while(i+ans<SZ) {
int L=pos[val][i], R=pos[val][i+ans];
int mini=nega.get(R, n).mn-nega.get(0, L-1).mx;
int maxi=posi.get(R, n).mx-posi.get(0, L-1).mn;
if(mini<=0 && maxi>=0) ans++;
else break;
}
}
}
return ans;
}
Compilation message
sequence.cpp: In member function 'node ST::build(int, int, int)':
sequence.cpp:23:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
23 | int mid=l+r>>1;
| ~^~
sequence.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
sequence.cpp:39:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | push(pos); int mid=l+r>>1;
| ~^~
sequence.cpp: In member function 'node ST::get(int, int, int, int, int)':
sequence.cpp:47:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
47 | push(pos);int mid=l+r>>1;
| ~^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33372 KB |
Output is correct |
2 |
Correct |
7 ms |
33368 KB |
Output is correct |
3 |
Correct |
6 ms |
33372 KB |
Output is correct |
4 |
Correct |
6 ms |
33372 KB |
Output is correct |
5 |
Correct |
7 ms |
33444 KB |
Output is correct |
6 |
Correct |
7 ms |
33372 KB |
Output is correct |
7 |
Correct |
7 ms |
33372 KB |
Output is correct |
8 |
Correct |
7 ms |
33372 KB |
Output is correct |
9 |
Correct |
7 ms |
33432 KB |
Output is correct |
10 |
Correct |
7 ms |
33372 KB |
Output is correct |
11 |
Correct |
7 ms |
33428 KB |
Output is correct |
12 |
Correct |
6 ms |
33368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33372 KB |
Output is correct |
2 |
Correct |
7 ms |
33368 KB |
Output is correct |
3 |
Correct |
6 ms |
33372 KB |
Output is correct |
4 |
Correct |
6 ms |
33372 KB |
Output is correct |
5 |
Correct |
7 ms |
33444 KB |
Output is correct |
6 |
Correct |
7 ms |
33372 KB |
Output is correct |
7 |
Correct |
7 ms |
33372 KB |
Output is correct |
8 |
Correct |
7 ms |
33372 KB |
Output is correct |
9 |
Correct |
7 ms |
33432 KB |
Output is correct |
10 |
Correct |
7 ms |
33372 KB |
Output is correct |
11 |
Correct |
7 ms |
33428 KB |
Output is correct |
12 |
Correct |
6 ms |
33368 KB |
Output is correct |
13 |
Correct |
8 ms |
33624 KB |
Output is correct |
14 |
Correct |
7 ms |
33372 KB |
Output is correct |
15 |
Correct |
8 ms |
33372 KB |
Output is correct |
16 |
Correct |
8 ms |
33368 KB |
Output is correct |
17 |
Correct |
8 ms |
33368 KB |
Output is correct |
18 |
Correct |
7 ms |
33368 KB |
Output is correct |
19 |
Correct |
7 ms |
33372 KB |
Output is correct |
20 |
Correct |
7 ms |
33372 KB |
Output is correct |
21 |
Correct |
8 ms |
33372 KB |
Output is correct |
22 |
Correct |
7 ms |
33424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33372 KB |
Output is correct |
2 |
Correct |
292 ms |
67140 KB |
Output is correct |
3 |
Correct |
294 ms |
67232 KB |
Output is correct |
4 |
Correct |
359 ms |
59400 KB |
Output is correct |
5 |
Correct |
292 ms |
66132 KB |
Output is correct |
6 |
Correct |
289 ms |
66132 KB |
Output is correct |
7 |
Correct |
280 ms |
59784 KB |
Output is correct |
8 |
Correct |
317 ms |
61300 KB |
Output is correct |
9 |
Correct |
376 ms |
60904 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33368 KB |
Output is correct |
2 |
Correct |
444 ms |
60260 KB |
Output is correct |
3 |
Correct |
487 ms |
59408 KB |
Output is correct |
4 |
Correct |
491 ms |
60384 KB |
Output is correct |
5 |
Correct |
594 ms |
61184 KB |
Output is correct |
6 |
Correct |
527 ms |
60352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
421 ms |
73136 KB |
Output is correct |
2 |
Correct |
401 ms |
72948 KB |
Output is correct |
3 |
Correct |
416 ms |
72532 KB |
Output is correct |
4 |
Correct |
413 ms |
72252 KB |
Output is correct |
5 |
Correct |
440 ms |
69148 KB |
Output is correct |
6 |
Correct |
431 ms |
72252 KB |
Output is correct |
7 |
Correct |
383 ms |
71080 KB |
Output is correct |
8 |
Correct |
337 ms |
70992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33372 KB |
Output is correct |
2 |
Correct |
7 ms |
33368 KB |
Output is correct |
3 |
Correct |
6 ms |
33372 KB |
Output is correct |
4 |
Correct |
6 ms |
33372 KB |
Output is correct |
5 |
Correct |
7 ms |
33444 KB |
Output is correct |
6 |
Correct |
7 ms |
33372 KB |
Output is correct |
7 |
Correct |
7 ms |
33372 KB |
Output is correct |
8 |
Correct |
7 ms |
33372 KB |
Output is correct |
9 |
Correct |
7 ms |
33432 KB |
Output is correct |
10 |
Correct |
7 ms |
33372 KB |
Output is correct |
11 |
Correct |
7 ms |
33428 KB |
Output is correct |
12 |
Correct |
6 ms |
33368 KB |
Output is correct |
13 |
Correct |
8 ms |
33624 KB |
Output is correct |
14 |
Correct |
7 ms |
33372 KB |
Output is correct |
15 |
Correct |
8 ms |
33372 KB |
Output is correct |
16 |
Correct |
8 ms |
33368 KB |
Output is correct |
17 |
Correct |
8 ms |
33368 KB |
Output is correct |
18 |
Correct |
7 ms |
33368 KB |
Output is correct |
19 |
Correct |
7 ms |
33372 KB |
Output is correct |
20 |
Correct |
7 ms |
33372 KB |
Output is correct |
21 |
Correct |
8 ms |
33372 KB |
Output is correct |
22 |
Correct |
7 ms |
33424 KB |
Output is correct |
23 |
Correct |
61 ms |
42076 KB |
Output is correct |
24 |
Correct |
63 ms |
42076 KB |
Output is correct |
25 |
Correct |
59 ms |
42096 KB |
Output is correct |
26 |
Correct |
72 ms |
40860 KB |
Output is correct |
27 |
Correct |
76 ms |
41044 KB |
Output is correct |
28 |
Correct |
73 ms |
40988 KB |
Output is correct |
29 |
Correct |
71 ms |
40540 KB |
Output is correct |
30 |
Correct |
71 ms |
40536 KB |
Output is correct |
31 |
Correct |
92 ms |
41176 KB |
Output is correct |
32 |
Correct |
47 ms |
42840 KB |
Output is correct |
33 |
Correct |
62 ms |
41812 KB |
Output is correct |
34 |
Correct |
68 ms |
41820 KB |
Output is correct |
35 |
Correct |
64 ms |
41820 KB |
Output is correct |
36 |
Correct |
65 ms |
41820 KB |
Output is correct |
37 |
Correct |
61 ms |
41880 KB |
Output is correct |
38 |
Correct |
65 ms |
41920 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
33372 KB |
Output is correct |
2 |
Correct |
7 ms |
33368 KB |
Output is correct |
3 |
Correct |
6 ms |
33372 KB |
Output is correct |
4 |
Correct |
6 ms |
33372 KB |
Output is correct |
5 |
Correct |
7 ms |
33444 KB |
Output is correct |
6 |
Correct |
7 ms |
33372 KB |
Output is correct |
7 |
Correct |
7 ms |
33372 KB |
Output is correct |
8 |
Correct |
7 ms |
33372 KB |
Output is correct |
9 |
Correct |
7 ms |
33432 KB |
Output is correct |
10 |
Correct |
7 ms |
33372 KB |
Output is correct |
11 |
Correct |
7 ms |
33428 KB |
Output is correct |
12 |
Correct |
6 ms |
33368 KB |
Output is correct |
13 |
Correct |
8 ms |
33624 KB |
Output is correct |
14 |
Correct |
7 ms |
33372 KB |
Output is correct |
15 |
Correct |
8 ms |
33372 KB |
Output is correct |
16 |
Correct |
8 ms |
33368 KB |
Output is correct |
17 |
Correct |
8 ms |
33368 KB |
Output is correct |
18 |
Correct |
7 ms |
33368 KB |
Output is correct |
19 |
Correct |
7 ms |
33372 KB |
Output is correct |
20 |
Correct |
7 ms |
33372 KB |
Output is correct |
21 |
Correct |
8 ms |
33372 KB |
Output is correct |
22 |
Correct |
7 ms |
33424 KB |
Output is correct |
23 |
Correct |
292 ms |
67140 KB |
Output is correct |
24 |
Correct |
294 ms |
67232 KB |
Output is correct |
25 |
Correct |
359 ms |
59400 KB |
Output is correct |
26 |
Correct |
292 ms |
66132 KB |
Output is correct |
27 |
Correct |
289 ms |
66132 KB |
Output is correct |
28 |
Correct |
280 ms |
59784 KB |
Output is correct |
29 |
Correct |
317 ms |
61300 KB |
Output is correct |
30 |
Correct |
376 ms |
60904 KB |
Output is correct |
31 |
Correct |
444 ms |
60260 KB |
Output is correct |
32 |
Correct |
487 ms |
59408 KB |
Output is correct |
33 |
Correct |
491 ms |
60384 KB |
Output is correct |
34 |
Correct |
594 ms |
61184 KB |
Output is correct |
35 |
Correct |
527 ms |
60352 KB |
Output is correct |
36 |
Correct |
421 ms |
73136 KB |
Output is correct |
37 |
Correct |
401 ms |
72948 KB |
Output is correct |
38 |
Correct |
416 ms |
72532 KB |
Output is correct |
39 |
Correct |
413 ms |
72252 KB |
Output is correct |
40 |
Correct |
440 ms |
69148 KB |
Output is correct |
41 |
Correct |
431 ms |
72252 KB |
Output is correct |
42 |
Correct |
383 ms |
71080 KB |
Output is correct |
43 |
Correct |
337 ms |
70992 KB |
Output is correct |
44 |
Correct |
61 ms |
42076 KB |
Output is correct |
45 |
Correct |
63 ms |
42076 KB |
Output is correct |
46 |
Correct |
59 ms |
42096 KB |
Output is correct |
47 |
Correct |
72 ms |
40860 KB |
Output is correct |
48 |
Correct |
76 ms |
41044 KB |
Output is correct |
49 |
Correct |
73 ms |
40988 KB |
Output is correct |
50 |
Correct |
71 ms |
40540 KB |
Output is correct |
51 |
Correct |
71 ms |
40536 KB |
Output is correct |
52 |
Correct |
92 ms |
41176 KB |
Output is correct |
53 |
Correct |
47 ms |
42840 KB |
Output is correct |
54 |
Correct |
62 ms |
41812 KB |
Output is correct |
55 |
Correct |
68 ms |
41820 KB |
Output is correct |
56 |
Correct |
64 ms |
41820 KB |
Output is correct |
57 |
Correct |
65 ms |
41820 KB |
Output is correct |
58 |
Correct |
61 ms |
41880 KB |
Output is correct |
59 |
Correct |
65 ms |
41920 KB |
Output is correct |
60 |
Correct |
566 ms |
70740 KB |
Output is correct |
61 |
Correct |
558 ms |
70536 KB |
Output is correct |
62 |
Correct |
562 ms |
70548 KB |
Output is correct |
63 |
Correct |
576 ms |
62548 KB |
Output is correct |
64 |
Correct |
575 ms |
62368 KB |
Output is correct |
65 |
Correct |
587 ms |
62152 KB |
Output is correct |
66 |
Correct |
470 ms |
60360 KB |
Output is correct |
67 |
Correct |
481 ms |
60600 KB |
Output is correct |
68 |
Correct |
600 ms |
62788 KB |
Output is correct |
69 |
Correct |
279 ms |
76116 KB |
Output is correct |
70 |
Correct |
553 ms |
69428 KB |
Output is correct |
71 |
Correct |
574 ms |
69356 KB |
Output is correct |
72 |
Correct |
595 ms |
68900 KB |
Output is correct |
73 |
Correct |
561 ms |
69188 KB |
Output is correct |
74 |
Correct |
543 ms |
69064 KB |
Output is correct |
75 |
Correct |
610 ms |
69160 KB |
Output is correct |