#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(40 * n, 0), R.assign(40 * n, 0);
root.assign(40 * n, 0), t.assign(40 * 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) {
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)) v.push_back(a[i] - x + 1), mp[a[i]];
}
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;
t.upd(mp[a[i]], dp);
chmax(res, dp + pst.get(idx, mp[a[i] - x + 1]));
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
720 ms |
148964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
143 ms |
70724 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
333 ms |
141872 KB |
Output is correct |
| 2 |
Correct |
379 ms |
141868 KB |
Output is correct |
| 3 |
Runtime error |
253 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
