#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;
#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0);
#define iter(a) a.begin(), a.end()
#define pb(a) emplace_back(a)
#define mp(a, b) make_pair(a, b)
#define ff first
#define ss second
#define topos(a) ((a) = (((a) % MOD + MOD) % MOD))
#define uni(a) a.resize(unique(iter(a)) - a.begin())
#define SZ(a) int(a.size())
#ifdef LOCAL
void debug(){cerr << "\n";}
template<class T, class ... U> void debug(T a, U ... b){cerr << a << " ", debug(b...);}
template<class T> void pary(T l, T r) {
while (l != r) cerr << *l << " ", l++;
cerr << "\n";
}
#else
#define debug(...) void()
#define pary(...) void()
#endif
typedef long long ll;
typedef long double ld;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const ll MOD = 1000000007;
const ll MAX = 2147483647;
template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
return o << '(' << p.ff << ',' << p.ss << ')';
}
ll ifloor(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a < 0) return (a - b + 1) / b;
else return a / b;
}
ll iceil(ll a, ll b){
if(b < 0) a *= -1, b *= -1;
if(a > 0) return (a + b - 1) / b;
else return a / b;
}
#define lc 2 * id
#define rc 2 * id + 1
int n;
struct Node{
int mn = 0, mx = 0, tag = 0;
};
struct SegTree{
vector<Node> st;
SegTree(): st(4 * n) {}
void addtag(int v, int id){
st[id].mn += v;
st[id].mx += v;
st[id].tag += v;
}
void push(int id){
addtag(st[id].tag, lc);
addtag(st[id].tag, rc);
st[id].tag = 0;
}
void pull(int id){
st[id].mn = min(st[lc].mn, st[rc].mn);
st[id].mx = max(st[lc].mx, st[rc].mx);
}
void modify(int l, int r, int v, int L = -1, int R = n - 1, int id = 1){
if(l <= L && R <= r){
addtag(v, id);
return;
}
push(id);
int M = ifloor(L + R, 2);
if(r <= M) modify(l, r, v, L, M, lc);
else if(l > M) modify(l, r, v, M + 1, R, rc);
else{
modify(l, r, v, L, M, lc);
modify(l, r, v, M + 1, R, rc);
}
pull(id);
}
int querymn(int l, int r, int L = -1, int R = n - 1, int id = 1){
if(l <= L && R <= r) return st[id].mn;
push(id);
int M = ifloor(L + R, 2);
if(r <= M) return querymn(l, r, L, M, lc);
else if(l > M) return querymn(l, r, M + 1, R, rc);
else return min(querymn(l, r, L, M, lc), querymn(l, r, M + 1, R, rc));
}
int querymx(int l, int r, int L = -1, int R = n - 1, int id = 1){
if(l <= L && R <= r) return st[id].mx;
push(id);
int M = ifloor(L + R, 2);
if(r <= M) return querymx(l, r, L, M, lc);
else if(l > M) return querymx(l, r, M + 1, R, rc);
else return max(querymx(l, r, L, M, lc), querymx(l, r, M + 1, R, rc));
}
void _print(int L = -1, int R = n - 1, int id = 1){
if(L == R){
cerr << st[id].mn << " ";
return;
}
push(id);
int M = ifloor(L + R, 2);
_print(L, M, lc);
_print(M + 1, R, rc);
}
void print(){
_print();
cerr << "\n";
}
};
int lowbit(int x){
return x & -x;
}
struct BIT{
vector<int> bit;
explicit BIT(int sz): bit(sz + 1, INT_MAX) {};
void modify(int x, int v){
x++;
for(; x < SZ(bit); x += lowbit(x)) bit[x] = min(bit[x], v);
}
int query(int x){
x++;
int ans = INT_MAX;
for(; x > 0; x -= lowbit(x)) ans = min(ans, bit[x]);
return ans;
}
};
struct item{
int x, y, type, i;
bool operator<(item b){
if(x != b.x) return x < b.x;
if(y != b.y) return y < b.y;
if(type != b.type) return type < b.type;
return i < b.i;
}
};
int sequence(int N, vector<int> A){
n = N;
SegTree seg;
vector<vector<int>> pos(n + 1);
for(int i = 0; i < n; i++){
pos[A[i]].pb(i);
seg.modify(i, n - 1, 1);
}
int ans = 0;
for(int v = 1; v <= n; v++){
for(int i : pos[v]) seg.modify(i, n - 1, -1);
//debug("start", v);
//seg.print();
vector<item> ev;
vector<int> discr;
int lst = -1;
for(int i = 0; i < SZ(pos[v]); i++){
int j = pos[v][i];
int nxt = i + 1 == SZ(pos[v]) ? n : pos[v][i + 1];
{
int mn = seg.querymn(lst, j - 1);
int mx = seg.querymx(lst, j - 1);
int x = i - mx, y = i + mn;
//debug("left", j, mn, mx, x, y);
discr.pb(y);
ev.pb(item({x, y, 0, i}));
}
{
int mn = seg.querymn(j, nxt - 1);
int mx = seg.querymx(j, nxt - 1);
int x = i - mn + 1, y = i + mx + 1;
//debug("right", j, mn, mx, x, y);
discr.pb(y);
ev.pb(item({x, y, 1, i}));
}
lst = j;
}
for(int i : pos[v]) seg.modify(i, n - 1, -1);
sort(iter(discr));
uni(discr);
sort(iter(ev));
BIT bit(SZ(discr));
for(auto [x, y, ty, i] : ev){
//debug("process", x, y, ty, i);
int id = lower_bound(iter(discr), y) - discr.begin();
if(ty == 0){
bit.modify(id, i);
}
else{
int j = bit.query(id);
if(j == INT_MAX) continue;
ans = max(ans, i - j + 1);
//debug("ans", i, j);
}
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
3 ms |
488 KB |
Output is correct |
15 |
Correct |
3 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
480 KB |
Output is correct |
17 |
Correct |
3 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
4 ms |
468 KB |
Output is correct |
21 |
Correct |
3 ms |
468 KB |
Output is correct |
22 |
Correct |
5 ms |
468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
687 ms |
49364 KB |
Output is correct |
3 |
Correct |
695 ms |
49352 KB |
Output is correct |
4 |
Correct |
680 ms |
48656 KB |
Output is correct |
5 |
Correct |
693 ms |
48420 KB |
Output is correct |
6 |
Correct |
668 ms |
48428 KB |
Output is correct |
7 |
Correct |
645 ms |
42652 KB |
Output is correct |
8 |
Correct |
642 ms |
42804 KB |
Output is correct |
9 |
Correct |
670 ms |
53968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
708 ms |
63924 KB |
Output is correct |
3 |
Correct |
733 ms |
54792 KB |
Output is correct |
4 |
Correct |
690 ms |
54836 KB |
Output is correct |
5 |
Correct |
701 ms |
66496 KB |
Output is correct |
6 |
Correct |
646 ms |
57340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
916 ms |
55096 KB |
Output is correct |
2 |
Correct |
871 ms |
54984 KB |
Output is correct |
3 |
Correct |
887 ms |
54516 KB |
Output is correct |
4 |
Correct |
921 ms |
54516 KB |
Output is correct |
5 |
Correct |
813 ms |
51180 KB |
Output is correct |
6 |
Correct |
853 ms |
51176 KB |
Output is correct |
7 |
Correct |
742 ms |
49988 KB |
Output is correct |
8 |
Correct |
731 ms |
49664 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
3 ms |
488 KB |
Output is correct |
15 |
Correct |
3 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
480 KB |
Output is correct |
17 |
Correct |
3 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
4 ms |
468 KB |
Output is correct |
21 |
Correct |
3 ms |
468 KB |
Output is correct |
22 |
Correct |
5 ms |
468 KB |
Output is correct |
23 |
Correct |
135 ms |
8148 KB |
Output is correct |
24 |
Correct |
129 ms |
8144 KB |
Output is correct |
25 |
Correct |
150 ms |
8184 KB |
Output is correct |
26 |
Correct |
130 ms |
7252 KB |
Output is correct |
27 |
Correct |
139 ms |
7256 KB |
Output is correct |
28 |
Correct |
127 ms |
7252 KB |
Output is correct |
29 |
Correct |
102 ms |
7880 KB |
Output is correct |
30 |
Correct |
100 ms |
7928 KB |
Output is correct |
31 |
Correct |
93 ms |
12532 KB |
Output is correct |
32 |
Correct |
98 ms |
9068 KB |
Output is correct |
33 |
Correct |
130 ms |
8732 KB |
Output is correct |
34 |
Correct |
132 ms |
8740 KB |
Output is correct |
35 |
Correct |
135 ms |
8520 KB |
Output is correct |
36 |
Correct |
125 ms |
8564 KB |
Output is correct |
37 |
Correct |
124 ms |
8592 KB |
Output is correct |
38 |
Correct |
129 ms |
8744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 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 |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
3 ms |
468 KB |
Output is correct |
14 |
Correct |
3 ms |
488 KB |
Output is correct |
15 |
Correct |
3 ms |
468 KB |
Output is correct |
16 |
Correct |
3 ms |
480 KB |
Output is correct |
17 |
Correct |
3 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
468 KB |
Output is correct |
19 |
Correct |
3 ms |
468 KB |
Output is correct |
20 |
Correct |
4 ms |
468 KB |
Output is correct |
21 |
Correct |
3 ms |
468 KB |
Output is correct |
22 |
Correct |
5 ms |
468 KB |
Output is correct |
23 |
Correct |
687 ms |
49364 KB |
Output is correct |
24 |
Correct |
695 ms |
49352 KB |
Output is correct |
25 |
Correct |
680 ms |
48656 KB |
Output is correct |
26 |
Correct |
693 ms |
48420 KB |
Output is correct |
27 |
Correct |
668 ms |
48428 KB |
Output is correct |
28 |
Correct |
645 ms |
42652 KB |
Output is correct |
29 |
Correct |
642 ms |
42804 KB |
Output is correct |
30 |
Correct |
670 ms |
53968 KB |
Output is correct |
31 |
Correct |
708 ms |
63924 KB |
Output is correct |
32 |
Correct |
733 ms |
54792 KB |
Output is correct |
33 |
Correct |
690 ms |
54836 KB |
Output is correct |
34 |
Correct |
701 ms |
66496 KB |
Output is correct |
35 |
Correct |
646 ms |
57340 KB |
Output is correct |
36 |
Correct |
916 ms |
55096 KB |
Output is correct |
37 |
Correct |
871 ms |
54984 KB |
Output is correct |
38 |
Correct |
887 ms |
54516 KB |
Output is correct |
39 |
Correct |
921 ms |
54516 KB |
Output is correct |
40 |
Correct |
813 ms |
51180 KB |
Output is correct |
41 |
Correct |
853 ms |
51176 KB |
Output is correct |
42 |
Correct |
742 ms |
49988 KB |
Output is correct |
43 |
Correct |
731 ms |
49664 KB |
Output is correct |
44 |
Correct |
135 ms |
8148 KB |
Output is correct |
45 |
Correct |
129 ms |
8144 KB |
Output is correct |
46 |
Correct |
150 ms |
8184 KB |
Output is correct |
47 |
Correct |
130 ms |
7252 KB |
Output is correct |
48 |
Correct |
139 ms |
7256 KB |
Output is correct |
49 |
Correct |
127 ms |
7252 KB |
Output is correct |
50 |
Correct |
102 ms |
7880 KB |
Output is correct |
51 |
Correct |
100 ms |
7928 KB |
Output is correct |
52 |
Correct |
93 ms |
12532 KB |
Output is correct |
53 |
Correct |
98 ms |
9068 KB |
Output is correct |
54 |
Correct |
130 ms |
8732 KB |
Output is correct |
55 |
Correct |
132 ms |
8740 KB |
Output is correct |
56 |
Correct |
135 ms |
8520 KB |
Output is correct |
57 |
Correct |
125 ms |
8564 KB |
Output is correct |
58 |
Correct |
124 ms |
8592 KB |
Output is correct |
59 |
Correct |
129 ms |
8744 KB |
Output is correct |
60 |
Correct |
1159 ms |
49360 KB |
Output is correct |
61 |
Correct |
1202 ms |
49372 KB |
Output is correct |
62 |
Correct |
1052 ms |
49364 KB |
Output is correct |
63 |
Correct |
948 ms |
42704 KB |
Output is correct |
64 |
Correct |
937 ms |
42720 KB |
Output is correct |
65 |
Correct |
962 ms |
42672 KB |
Output is correct |
66 |
Correct |
747 ms |
48608 KB |
Output is correct |
67 |
Correct |
728 ms |
48632 KB |
Output is correct |
68 |
Correct |
687 ms |
65020 KB |
Output is correct |
69 |
Correct |
678 ms |
55144 KB |
Output is correct |
70 |
Correct |
1105 ms |
51276 KB |
Output is correct |
71 |
Correct |
1080 ms |
53944 KB |
Output is correct |
72 |
Correct |
1051 ms |
53424 KB |
Output is correct |
73 |
Correct |
1046 ms |
53728 KB |
Output is correct |
74 |
Correct |
993 ms |
53348 KB |
Output is correct |
75 |
Correct |
1010 ms |
53724 KB |
Output is correct |