#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using vi = vector<int>;
using oset = tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>;
const int R = (1 << 19);
vi t(R * 2, 0);
void update(int i, int x) {
int v = R + i;
t[v] = x;
v >>= 1;
while (v > 0) {
t[v] = max(t[v << 1], t[(v << 1) ^ 1]);
v >>= 1;
}
}
int get_max(int l, int r) {
l += R;
r += R;
int res = 0;
while (l < r) {
if (l & 1) {
res = max(res, t[l]);
++l;
}
if (!(r & 1)) {
res = max(res, t[r]);
--r;
}
l >>= 1;
r >>= 1;
}
if (l == r)
res = max(res, t[l]);
return res;
}
vi t1(R * 2, R);
void update1(int ql, int qr, int x, int v = 1, int l = 0, int r = R) {
if (ql >= r || l >= qr)
return;
if (ql <= l && r <= qr) {
t1[v] = min(t1[v], x);
return;
}
int m = (l + r) / 2;
update1(ql, qr, x, (v << 1), l, m);
update1(ql, qr, x, ((v << 1) ^ 1), m, r);
}
int get1(int i) {
int v = R + i, res = R;
while (v > 0) {
res = min(res, t1[v]);
v >>= 1;
}
return res;
}
void compress(vi &a) {
vi b = a;
sort(all(b));
for (int &x: a)
x = lower_bound(all(b), x) - b.begin();
}
int main() {
fast;
int n, d;
cin >> n >> d;
vi a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
compress(a);
vi r(n);
multiset<int> s;
for (int i = n - d; i < n; ++i) {
r[i] = n;
s.insert(a[i]);
}
for (int i = n - d - 1; i >= 0; --i) {
update1(0, *s.begin(), i);
r[i] = min(get1(a[i]) + d, n);
s.erase(s.find(a[i + d]));
s.insert(a[i]);
}
vi b(n);
vector<multiset<int>> c(n);
for (int i = 0; i < n; ++i)
c[i].insert(0);
multiset<tuple<int, int, int>> ss;
for (int i = 0; i < n; ++i) {
b[i] = get_max(0, a[i] - 1) + 1;
ss.emplace(r[i], a[i], b[i]);
c[a[i]].insert(b[i]);
update(a[i], *(--c[a[i]].end()));
while (!ss.empty() && get<0>(*ss.begin()) == i) {
c[get<1>(*ss.begin())].erase(c[get<1>(*ss.begin())].find(get<2>(*ss.begin())));
update(get<1>(*ss.begin()), *(--c[get<1>(*ss.begin())].end()));
ss.erase(ss.begin());
}
}
int ans = 0;
for (int i = max(n - d - 1, 0); i < n; ++i)
ans = max(ans, b[i]);
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8540 KB |
Output is correct |
2 |
Correct |
3 ms |
8688 KB |
Output is correct |
3 |
Correct |
4 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
4 ms |
9052 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
3 ms |
8540 KB |
Output is correct |
8 |
Correct |
4 ms |
8540 KB |
Output is correct |
9 |
Correct |
3 ms |
8680 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
3 ms |
8536 KB |
Output is correct |
12 |
Correct |
3 ms |
8536 KB |
Output is correct |
13 |
Correct |
3 ms |
8540 KB |
Output is correct |
14 |
Correct |
3 ms |
8540 KB |
Output is correct |
15 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8540 KB |
Output is correct |
2 |
Correct |
3 ms |
8688 KB |
Output is correct |
3 |
Correct |
4 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
4 ms |
9052 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
3 ms |
8540 KB |
Output is correct |
8 |
Correct |
4 ms |
8540 KB |
Output is correct |
9 |
Correct |
3 ms |
8680 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
3 ms |
8536 KB |
Output is correct |
12 |
Correct |
3 ms |
8536 KB |
Output is correct |
13 |
Correct |
3 ms |
8540 KB |
Output is correct |
14 |
Correct |
3 ms |
8540 KB |
Output is correct |
15 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8540 KB |
Output is correct |
2 |
Correct |
3 ms |
8688 KB |
Output is correct |
3 |
Correct |
4 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
4 ms |
9052 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
3 ms |
8540 KB |
Output is correct |
8 |
Correct |
4 ms |
8540 KB |
Output is correct |
9 |
Correct |
3 ms |
8680 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
3 ms |
8536 KB |
Output is correct |
12 |
Correct |
3 ms |
8536 KB |
Output is correct |
13 |
Correct |
3 ms |
8540 KB |
Output is correct |
14 |
Correct |
3 ms |
8540 KB |
Output is correct |
15 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
224 ms |
76184 KB |
Output is correct |
2 |
Incorrect |
177 ms |
47548 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
90560 KB |
Output is correct |
2 |
Correct |
468 ms |
90196 KB |
Output is correct |
3 |
Correct |
687 ms |
90348 KB |
Output is correct |
4 |
Correct |
683 ms |
90156 KB |
Output is correct |
5 |
Correct |
551 ms |
90236 KB |
Output is correct |
6 |
Correct |
710 ms |
90176 KB |
Output is correct |
7 |
Correct |
225 ms |
90048 KB |
Output is correct |
8 |
Correct |
215 ms |
90084 KB |
Output is correct |
9 |
Correct |
249 ms |
89540 KB |
Output is correct |
10 |
Correct |
397 ms |
89784 KB |
Output is correct |
11 |
Correct |
630 ms |
90096 KB |
Output is correct |
12 |
Correct |
472 ms |
90216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
8540 KB |
Output is correct |
2 |
Correct |
3 ms |
8688 KB |
Output is correct |
3 |
Correct |
4 ms |
8540 KB |
Output is correct |
4 |
Correct |
4 ms |
8540 KB |
Output is correct |
5 |
Correct |
4 ms |
9052 KB |
Output is correct |
6 |
Correct |
4 ms |
8540 KB |
Output is correct |
7 |
Correct |
3 ms |
8540 KB |
Output is correct |
8 |
Correct |
4 ms |
8540 KB |
Output is correct |
9 |
Correct |
3 ms |
8680 KB |
Output is correct |
10 |
Correct |
3 ms |
8540 KB |
Output is correct |
11 |
Correct |
3 ms |
8536 KB |
Output is correct |
12 |
Correct |
3 ms |
8536 KB |
Output is correct |
13 |
Correct |
3 ms |
8540 KB |
Output is correct |
14 |
Correct |
3 ms |
8540 KB |
Output is correct |
15 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
16 |
Halted |
0 ms |
0 KB |
- |