#pragma GCC optimize("Ofast")
#include "sequence.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) (int)(x.size())
#define itr(x) x.begin(), x.end()
#define ref(x) (*(x))
#ifdef LOC
#define debug(...) cerr << #__VA_ARGS__ << " : "; for(auto& dval : {__VA_ARGS__}) cerr << dval << " "; cerr << "\n";
#else
#define debug(...)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
ostream& operator << (ostream& out, vector<T> v) {
for(auto& i : v) {
out << i << " ";
}
return out;
}
struct node {
int lb, rb, mn, mx, lazy, lc, rc;
};
ostream& operator << (ostream& out, node v) {
cout << v.lb << " " << v.rb << " " << v.mn << " " << v.mx << " " << v.lazy << " " << v.lc << " " << v.rc << " ";
return out;
}
struct segtree {
vector<node> nodes;
segtree(int l, int r) {
nodes.reserve((r - l + 1) * 2);
build(l, r);
}
void build(int l, int r) {
int idx = sz(nodes);
nodes.push_back({l, r, l, r, 0, -1, -1});
if(l == r) {
return;
}
int mid = (l + r) / 2;
nodes[idx].lc = sz(nodes);
build(l, mid);
nodes[idx].rc = sz(nodes);
build(mid + 1, r);
}
void sadd(int l, int r, int v, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return;
}
if(l <= lb && r >= rb) {
nodes[idx].lazy += v;
return;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc;
sadd(l, r, v, lc);
sadd(l, r, v, rc);
nodes[idx].mx = max(nodes[lc].mx + nodes[lc].lazy, nodes[rc].mx + nodes[rc].lazy);
nodes[idx].mn = min(nodes[lc].mn + nodes[lc].lazy, nodes[rc].mn + nodes[rc].lazy);
}
int qrymx(int l, int r, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return INT_MIN;
}
if(l <= lb && r >= rb) {
return nodes[idx].mx + nodes[idx].lazy;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
ret = max(qrymx(l, r, lc), qrymx(l, r, rc));
return ret + nodes[idx].lazy;
}
int qrymn(int l, int r, int idx = 0) {
int lb = nodes[idx].lb, rb = nodes[idx].rb;
if(r < lb || l > rb) {
return INT_MAX;
}
if(l <= lb && r >= rb) {
return nodes[idx].mn + nodes[idx].lazy;
}
int lc = nodes[idx].lc, rc = nodes[idx].rc, ret = 0;
ret = min(qrymn(l, r, lc), qrymn(l, r, rc));
return ret + nodes[idx].lazy;
}
};
int sequence(int N, std::vector<int> A) {
debug(N); debug(A);
vector<int> sids(N);
for(int i = 0; i < N; i++) {
sids[i] = i;
}
sort(sids.begin(), sids.end(), [&](int a, int b) {
if(A[a] != A[b]) {
return A[a] < A[b];
} else {
return a < b;
}
});
int ptr = 0, mx = 1;
segtree eqpos(0, N), eqneg(0, N);
while(ptr < N) {
for(int i = ptr; i < N && A[sids[i]] == A[sids[ptr]]; i++) {
eqneg.sadd(sids[i] + 1, N, -2);
}
int nptr = ptr;
while(nptr < N && A[sids[nptr]] == A[sids[ptr]]) {
if(nptr + mx >= N) {
return mx;
}
int l = sids[nptr], r = sids[nptr + mx];
if(A[l] != A[r]) {
nptr++;
continue;
}
if(eqpos.qrymx(r + 1, N) - eqpos.qrymn(0, l) >= 0 && eqneg.qrymn(r + 1, N) - eqneg.qrymx(0, l) <= 0) {
mx++;
} else {
nptr++;
}
}
for(; ptr < nptr; ptr++) {
eqpos.sadd(sids[ptr] + 1, N, -2);
}
}
return mx;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
295 ms |
61000 KB |
Output is correct |
3 |
Correct |
298 ms |
60876 KB |
Output is correct |
4 |
Correct |
312 ms |
60924 KB |
Output is correct |
5 |
Correct |
301 ms |
61004 KB |
Output is correct |
6 |
Correct |
300 ms |
61016 KB |
Output is correct |
7 |
Correct |
253 ms |
60968 KB |
Output is correct |
8 |
Correct |
296 ms |
60972 KB |
Output is correct |
9 |
Correct |
295 ms |
60964 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
294 ms |
60960 KB |
Output is correct |
3 |
Correct |
422 ms |
61072 KB |
Output is correct |
4 |
Correct |
370 ms |
60888 KB |
Output is correct |
5 |
Correct |
511 ms |
60952 KB |
Output is correct |
6 |
Correct |
370 ms |
60976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
449 ms |
60960 KB |
Output is correct |
2 |
Correct |
444 ms |
60960 KB |
Output is correct |
3 |
Correct |
505 ms |
60872 KB |
Output is correct |
4 |
Correct |
526 ms |
60964 KB |
Output is correct |
5 |
Correct |
448 ms |
60968 KB |
Output is correct |
6 |
Correct |
438 ms |
60968 KB |
Output is correct |
7 |
Correct |
353 ms |
60968 KB |
Output is correct |
8 |
Correct |
327 ms |
60972 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
23 |
Correct |
68 ms |
10008 KB |
Output is correct |
24 |
Correct |
69 ms |
10012 KB |
Output is correct |
25 |
Correct |
72 ms |
9968 KB |
Output is correct |
26 |
Correct |
95 ms |
10012 KB |
Output is correct |
27 |
Correct |
90 ms |
9940 KB |
Output is correct |
28 |
Correct |
84 ms |
10008 KB |
Output is correct |
29 |
Correct |
63 ms |
10012 KB |
Output is correct |
30 |
Correct |
56 ms |
9940 KB |
Output is correct |
31 |
Correct |
57 ms |
10012 KB |
Output is correct |
32 |
Correct |
43 ms |
10016 KB |
Output is correct |
33 |
Correct |
65 ms |
10012 KB |
Output is correct |
34 |
Correct |
68 ms |
10016 KB |
Output is correct |
35 |
Correct |
62 ms |
10016 KB |
Output is correct |
36 |
Correct |
67 ms |
10012 KB |
Output is correct |
37 |
Correct |
72 ms |
9972 KB |
Output is correct |
38 |
Correct |
69 ms |
9940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
212 KB |
Output is correct |
13 |
Correct |
2 ms |
468 KB |
Output is correct |
14 |
Correct |
2 ms |
468 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
1 ms |
468 KB |
Output is correct |
19 |
Correct |
1 ms |
468 KB |
Output is correct |
20 |
Correct |
1 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |
22 |
Correct |
2 ms |
468 KB |
Output is correct |
23 |
Correct |
295 ms |
61000 KB |
Output is correct |
24 |
Correct |
298 ms |
60876 KB |
Output is correct |
25 |
Correct |
312 ms |
60924 KB |
Output is correct |
26 |
Correct |
301 ms |
61004 KB |
Output is correct |
27 |
Correct |
300 ms |
61016 KB |
Output is correct |
28 |
Correct |
253 ms |
60968 KB |
Output is correct |
29 |
Correct |
296 ms |
60972 KB |
Output is correct |
30 |
Correct |
295 ms |
60964 KB |
Output is correct |
31 |
Correct |
294 ms |
60960 KB |
Output is correct |
32 |
Correct |
422 ms |
61072 KB |
Output is correct |
33 |
Correct |
370 ms |
60888 KB |
Output is correct |
34 |
Correct |
511 ms |
60952 KB |
Output is correct |
35 |
Correct |
370 ms |
60976 KB |
Output is correct |
36 |
Correct |
449 ms |
60960 KB |
Output is correct |
37 |
Correct |
444 ms |
60960 KB |
Output is correct |
38 |
Correct |
505 ms |
60872 KB |
Output is correct |
39 |
Correct |
526 ms |
60964 KB |
Output is correct |
40 |
Correct |
448 ms |
60968 KB |
Output is correct |
41 |
Correct |
438 ms |
60968 KB |
Output is correct |
42 |
Correct |
353 ms |
60968 KB |
Output is correct |
43 |
Correct |
327 ms |
60972 KB |
Output is correct |
44 |
Correct |
68 ms |
10008 KB |
Output is correct |
45 |
Correct |
69 ms |
10012 KB |
Output is correct |
46 |
Correct |
72 ms |
9968 KB |
Output is correct |
47 |
Correct |
95 ms |
10012 KB |
Output is correct |
48 |
Correct |
90 ms |
9940 KB |
Output is correct |
49 |
Correct |
84 ms |
10008 KB |
Output is correct |
50 |
Correct |
63 ms |
10012 KB |
Output is correct |
51 |
Correct |
56 ms |
9940 KB |
Output is correct |
52 |
Correct |
57 ms |
10012 KB |
Output is correct |
53 |
Correct |
43 ms |
10016 KB |
Output is correct |
54 |
Correct |
65 ms |
10012 KB |
Output is correct |
55 |
Correct |
68 ms |
10016 KB |
Output is correct |
56 |
Correct |
62 ms |
10016 KB |
Output is correct |
57 |
Correct |
67 ms |
10012 KB |
Output is correct |
58 |
Correct |
72 ms |
9972 KB |
Output is correct |
59 |
Correct |
69 ms |
9940 KB |
Output is correct |
60 |
Correct |
838 ms |
60964 KB |
Output is correct |
61 |
Correct |
841 ms |
60976 KB |
Output is correct |
62 |
Correct |
877 ms |
60972 KB |
Output is correct |
63 |
Correct |
943 ms |
60960 KB |
Output is correct |
64 |
Correct |
957 ms |
60972 KB |
Output is correct |
65 |
Correct |
954 ms |
60972 KB |
Output is correct |
66 |
Correct |
471 ms |
60976 KB |
Output is correct |
67 |
Correct |
448 ms |
61004 KB |
Output is correct |
68 |
Correct |
391 ms |
60968 KB |
Output is correct |
69 |
Correct |
240 ms |
61084 KB |
Output is correct |
70 |
Correct |
766 ms |
60960 KB |
Output is correct |
71 |
Correct |
786 ms |
60968 KB |
Output is correct |
72 |
Correct |
782 ms |
60968 KB |
Output is correct |
73 |
Correct |
875 ms |
60968 KB |
Output is correct |
74 |
Correct |
902 ms |
60964 KB |
Output is correct |
75 |
Correct |
894 ms |
60964 KB |
Output is correct |