#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) x.begin(), x.end()
#define size(x) (int)x.size()
template<class S, class T>
bool chmin(S &a, const T &b) {
return a > b ? (a = b) == b : false;
}
template<class S, class T>
bool chmax(S &a, const T &b) {
return a < b ? (a = b) == b : false;
}
struct PST {
int n, sz, cnt;
vector<int> L, R, root, t, a;
void construct(int n, vector<int> arr) {
this -> n = n;
a = arr, sz = 0, cnt = 1;
L.assign(35 * n, 0), R.assign(35 * n, 0);
root.assign(35 * n, 0), t.assign(35 * n, 0);
root[1] = build(1, n);
}
int build(int tl, int tr) {
int v = ++sz;
if (tl == tr) {
t[v] = a[tl];
return v;
}
int tm = (tl + tr) >> 1;
L[v] = build(tl, tm);
R[v] = build(tm + 1, tr);
t[v] = max(t[L[v]], t[R[v]]);
return v;
}
int upd(int v, int tl, int tr, int i, int x) {
int nv = ++sz;
L[nv] = L[v];
R[nv] = R[v];
if (tl == tr) {
t[nv] = x;
return nv;
}
int tm = (tl + tr) >> 1;
if (i <= tm) {
L[nv] = upd(L[nv], tl, tm, i, x);
} else {
R[nv] = upd(R[nv], tm + 1, tr, i, x);
}
t[nv] = max(t[L[nv]], t[R[nv]]);
return nv;
} void upd(int id, int i, int x) {
root[id] = upd(root[id], 1, n, i, x);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l) {
return 0ll;
}
if (tl >= l && tr <= r) {
return t[v];
}
int tm = (tl + tr) >> 1;
return max(get(L[v], tl, tm, l, r), get(R[v], tm + 1, tr, l, r));
} int get(int id, int l) {
if (l > n) return 0ll;
return get(root[id], 1, n, l, n);
}
void copy(int id) {
root[++cnt] = root[id];
}
};
struct segtree {
int n;
vector<int> t;
void construct(int n) {
this -> n = n;
t.assign(4 * n + 4, 0);
}
void upd(int v, int tl, int tr, int i, int delta) {
if (tl == tr) {
t[v] = delta;
return;
}
int tm = (tl + tr) / 2;
if (tm >= i) upd(2 * v, tl, tm, i, delta);
else upd(2 * v + 1, tm + 1, tr, i, delta);
t[v] = max(t[2 * v], t[2 * v + 1]);
} void upd(int i, int delta) {
upd(1, 1, n, i, delta);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l) return 0ll;
if (tl >= l && tr <= r) return t[v];
int tm = (tl + tr) / 2;
return max(get(2 * v, tl, tm, l, r), get(2 * v + 1, tm + 1, tr, l, r));
} int get(int l, int r) {
if (l > r) return 0ll;
return get(1, 1, n, l, r);
}
};
PST pst;
segtree t;
map<int, int> mp;
void compress(vector<int> a, int x) {
vector<int> v;
for (int i = 0; i < size(a); ++i) {
if (!mp.count(a[i])) v.push_back(a[i]), mp[a[i]];
if (!mp.count(a[i] - x + 1)) v.push_back(a[i] - x + 1), mp[a[i] - x + 1];
}
sort(all(v));
vector<int> constructor;
for (int i = 0; i < size(v); ++i) {
mp[v[i]] = i + 1;
constructor.push_back(0);
}
constructor.push_back(0);
pst.construct(size(v), constructor);
t.construct(size(v));
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, x; cin >> n >> x;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
compress(a, x);
for (int i = n - 1, idx = 2; i >= 0; --i, ++idx) {
pst.copy(idx - 1);
int dp = pst.get(idx, mp[a[i]] + 1) + 1;
pst.upd(idx, mp[a[i]], dp);
}
int res = 0;
for (int i = 0, idx = n; i < n; ++i, --idx) {
int dp = t.get(1, mp[a[i]] - 1) + 1;
t.upd(mp[a[i]], dp);
chmax(res, dp + pst.get(idx, mp[a[i] - x + 1]));
}
cout << res;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
2 ms |
1628 KB |
Output is correct |
20 |
Correct |
2 ms |
1628 KB |
Output is correct |
21 |
Correct |
2 ms |
1628 KB |
Output is correct |
22 |
Correct |
2 ms |
1624 KB |
Output is correct |
23 |
Correct |
2 ms |
1112 KB |
Output is correct |
24 |
Correct |
2 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
856 KB |
Output is correct |
26 |
Correct |
2 ms |
1116 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1100 ms |
250804 KB |
Output is correct |
2 |
Correct |
1099 ms |
250848 KB |
Output is correct |
3 |
Correct |
1061 ms |
250892 KB |
Output is correct |
4 |
Correct |
1002 ms |
250952 KB |
Output is correct |
5 |
Correct |
261 ms |
126400 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
146 ms |
63172 KB |
Output is correct |
2 |
Correct |
171 ms |
63208 KB |
Output is correct |
3 |
Correct |
139 ms |
62964 KB |
Output is correct |
4 |
Correct |
54 ms |
31896 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
48 ms |
16416 KB |
Output is correct |
7 |
Correct |
104 ms |
52740 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
334 ms |
125728 KB |
Output is correct |
2 |
Correct |
349 ms |
125692 KB |
Output is correct |
3 |
Correct |
919 ms |
250884 KB |
Output is correct |
4 |
Correct |
294 ms |
126516 KB |
Output is correct |
5 |
Correct |
203 ms |
125744 KB |
Output is correct |
6 |
Correct |
409 ms |
238764 KB |
Output is correct |
7 |
Correct |
379 ms |
238336 KB |
Output is correct |
8 |
Correct |
256 ms |
125648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
1 ms |
348 KB |
Output is correct |
15 |
Correct |
1 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
2 ms |
1628 KB |
Output is correct |
20 |
Correct |
2 ms |
1628 KB |
Output is correct |
21 |
Correct |
2 ms |
1628 KB |
Output is correct |
22 |
Correct |
2 ms |
1624 KB |
Output is correct |
23 |
Correct |
2 ms |
1112 KB |
Output is correct |
24 |
Correct |
2 ms |
1116 KB |
Output is correct |
25 |
Correct |
2 ms |
856 KB |
Output is correct |
26 |
Correct |
2 ms |
1116 KB |
Output is correct |
27 |
Correct |
1100 ms |
250804 KB |
Output is correct |
28 |
Correct |
1099 ms |
250848 KB |
Output is correct |
29 |
Correct |
1061 ms |
250892 KB |
Output is correct |
30 |
Correct |
1002 ms |
250952 KB |
Output is correct |
31 |
Correct |
261 ms |
126400 KB |
Output is correct |
32 |
Correct |
146 ms |
63172 KB |
Output is correct |
33 |
Correct |
171 ms |
63208 KB |
Output is correct |
34 |
Correct |
139 ms |
62964 KB |
Output is correct |
35 |
Correct |
54 ms |
31896 KB |
Output is correct |
36 |
Correct |
0 ms |
348 KB |
Output is correct |
37 |
Correct |
48 ms |
16416 KB |
Output is correct |
38 |
Correct |
104 ms |
52740 KB |
Output is correct |
39 |
Correct |
334 ms |
125728 KB |
Output is correct |
40 |
Correct |
349 ms |
125692 KB |
Output is correct |
41 |
Correct |
919 ms |
250884 KB |
Output is correct |
42 |
Correct |
294 ms |
126516 KB |
Output is correct |
43 |
Correct |
203 ms |
125744 KB |
Output is correct |
44 |
Correct |
409 ms |
238764 KB |
Output is correct |
45 |
Correct |
379 ms |
238336 KB |
Output is correct |
46 |
Correct |
256 ms |
125648 KB |
Output is correct |
47 |
Correct |
395 ms |
125680 KB |
Output is correct |
48 |
Correct |
380 ms |
125696 KB |
Output is correct |
49 |
Correct |
1032 ms |
250916 KB |
Output is correct |
50 |
Correct |
215 ms |
126516 KB |
Output is correct |
51 |
Correct |
227 ms |
95068 KB |
Output is correct |
52 |
Correct |
325 ms |
127004 KB |
Output is correct |
53 |
Correct |
414 ms |
251024 KB |
Output is correct |
54 |
Correct |
420 ms |
250876 KB |
Output is correct |
55 |
Correct |
563 ms |
209816 KB |
Output is correct |