#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))
#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)
using namespace std;
#define int long long int
#define lld long double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())
#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a)
void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
struct seg {
int n;
vector<int> v;
void init_(int _n) {
n = _n;
v.assign(2 * n + 1, 0);
}
int get(int L, int R) {
return (L + R) | (L != R);
}
void pull(int L, int R) {
int nd = get(L, R), mid = (L + R) / 2;
v[nd] = max(v[get(L, mid)], v[get(mid + 1, R)]);
}
void modify(int L, int R, int id, int val) {
int nd = get(L, R), mid = (L + R) / 2;
if(L == R) v[nd] = val;
else {
if(id <= mid) modify(L, mid, id, val);
else modify(mid + 1, R, id, val);
pull(L, R);
}
}
int query(int L, int R, int l, int r) {
int nd = get(L, R), mid = (L + R) / 2;
if(l > R || r < L) return 0;
else if(l <= L && r >= R) return v[nd];
else return max(query(L, mid, l, r), query(mid + 1, R, l, r));
}
};
namespace solver {
int n, d;
seg val, pos;
vector<set<pii>> s;
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<int> a, dp, v;
void init_(int _n, int _d) {
n = _n, d= _d;
val.init_(n);
pos.init_(n);
s.assign(n + 1, set<pii>());
a.assign(n + 1, 0);
dp.assign(n + 1, 0);
v.clear();
}
void insert(int x) {
s[a[x]].insert({dp[x], x});
pii best = *s[a[x]].rbegin();
val.modify(1, n, a[x], best.first);
}
void erase(int x) {
s[a[x]].erase(s[a[x]].find({dp[x], x}));
pii best = (s[a[x]].size() ? *s[a[x]].rbegin() : pii(0, 0));
val.modify(1, n, a[x], best.first);
}
bool check(int x, int y) {
return pos.query(1, n, 1, x) >= y;
}
int solve() {
rep(i, 1, n) v.push_back(a[i]);
sort(all(v)), v.resize(unique(all(v)) - v.begin());
rep(i, 1, n) a[i] = lower_bound(all(v), a[i]) - v.begin() + 1;
rep(i, 1, n) {
while(pq.size() && !check(pq.top().first, i)) {
erase(pq.top().second);
pq.pop();
}
dp[i] = val.query(1, n, 1, a[i] - 1) + 1;
pos.modify(1, n, a[i], i + d);
pq.push({a[i], i});
insert(i);
}
return val.query(1, n, 1, n);
}
};
using namespace solver;
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
int n, d; cin >> n >> d;
init_(n, d);
rep(i, 1, n) cin >> a[i];
cout << solve() << "\n";
return 0;
}
Compilation message
Main.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
4 | #pragma loop-opt(on)
|
Main.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
| ^~~~
Main.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
24 | void vprint(auto L, auto R) {while(L < R) cerr << *L << " \n"[next(L) == R], ++L; }
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
8 ms |
1100 KB |
Output is correct |
42 |
Correct |
9 ms |
972 KB |
Output is correct |
43 |
Correct |
6 ms |
1228 KB |
Output is correct |
44 |
Correct |
7 ms |
1228 KB |
Output is correct |
45 |
Correct |
9 ms |
1484 KB |
Output is correct |
46 |
Correct |
10 ms |
1484 KB |
Output is correct |
47 |
Correct |
8 ms |
1072 KB |
Output is correct |
48 |
Correct |
10 ms |
1144 KB |
Output is correct |
49 |
Correct |
9 ms |
1216 KB |
Output is correct |
50 |
Correct |
9 ms |
1228 KB |
Output is correct |
51 |
Correct |
8 ms |
1108 KB |
Output is correct |
52 |
Correct |
9 ms |
1108 KB |
Output is correct |
53 |
Correct |
7 ms |
1100 KB |
Output is correct |
54 |
Correct |
8 ms |
1108 KB |
Output is correct |
55 |
Correct |
7 ms |
1484 KB |
Output is correct |
56 |
Correct |
7 ms |
1484 KB |
Output is correct |
57 |
Correct |
7 ms |
1484 KB |
Output is correct |
58 |
Correct |
6 ms |
1484 KB |
Output is correct |
59 |
Correct |
6 ms |
1484 KB |
Output is correct |
60 |
Correct |
6 ms |
1484 KB |
Output is correct |
61 |
Correct |
6 ms |
1484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
241 ms |
55388 KB |
Output is correct |
2 |
Correct |
300 ms |
34100 KB |
Output is correct |
3 |
Correct |
347 ms |
32704 KB |
Output is correct |
4 |
Correct |
698 ms |
32716 KB |
Output is correct |
5 |
Correct |
508 ms |
32720 KB |
Output is correct |
6 |
Correct |
649 ms |
32712 KB |
Output is correct |
7 |
Correct |
310 ms |
32444 KB |
Output is correct |
8 |
Correct |
287 ms |
55368 KB |
Output is correct |
9 |
Correct |
324 ms |
32700 KB |
Output is correct |
10 |
Correct |
316 ms |
43360 KB |
Output is correct |
11 |
Correct |
449 ms |
32712 KB |
Output is correct |
12 |
Correct |
507 ms |
32828 KB |
Output is correct |
13 |
Correct |
522 ms |
32700 KB |
Output is correct |
14 |
Correct |
696 ms |
32704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
254 ms |
55472 KB |
Output is correct |
2 |
Correct |
355 ms |
55432 KB |
Output is correct |
3 |
Correct |
458 ms |
55480 KB |
Output is correct |
4 |
Correct |
575 ms |
55484 KB |
Output is correct |
5 |
Correct |
452 ms |
55476 KB |
Output is correct |
6 |
Correct |
530 ms |
55488 KB |
Output is correct |
7 |
Correct |
249 ms |
55452 KB |
Output is correct |
8 |
Correct |
267 ms |
55456 KB |
Output is correct |
9 |
Correct |
263 ms |
55348 KB |
Output is correct |
10 |
Correct |
364 ms |
55268 KB |
Output is correct |
11 |
Correct |
508 ms |
55548 KB |
Output is correct |
12 |
Correct |
424 ms |
55604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
0 ms |
204 KB |
Output is correct |
11 |
Correct |
0 ms |
204 KB |
Output is correct |
12 |
Correct |
1 ms |
204 KB |
Output is correct |
13 |
Correct |
0 ms |
204 KB |
Output is correct |
14 |
Correct |
1 ms |
204 KB |
Output is correct |
15 |
Correct |
0 ms |
204 KB |
Output is correct |
16 |
Correct |
1 ms |
204 KB |
Output is correct |
17 |
Correct |
0 ms |
204 KB |
Output is correct |
18 |
Correct |
1 ms |
204 KB |
Output is correct |
19 |
Correct |
1 ms |
204 KB |
Output is correct |
20 |
Correct |
0 ms |
204 KB |
Output is correct |
21 |
Correct |
1 ms |
204 KB |
Output is correct |
22 |
Correct |
1 ms |
204 KB |
Output is correct |
23 |
Correct |
1 ms |
204 KB |
Output is correct |
24 |
Correct |
1 ms |
204 KB |
Output is correct |
25 |
Correct |
1 ms |
204 KB |
Output is correct |
26 |
Correct |
1 ms |
204 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
332 KB |
Output is correct |
29 |
Correct |
1 ms |
332 KB |
Output is correct |
30 |
Correct |
1 ms |
332 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
1 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
1 ms |
332 KB |
Output is correct |
36 |
Correct |
1 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
332 KB |
Output is correct |
40 |
Correct |
1 ms |
332 KB |
Output is correct |
41 |
Correct |
8 ms |
1100 KB |
Output is correct |
42 |
Correct |
9 ms |
972 KB |
Output is correct |
43 |
Correct |
6 ms |
1228 KB |
Output is correct |
44 |
Correct |
7 ms |
1228 KB |
Output is correct |
45 |
Correct |
9 ms |
1484 KB |
Output is correct |
46 |
Correct |
10 ms |
1484 KB |
Output is correct |
47 |
Correct |
8 ms |
1072 KB |
Output is correct |
48 |
Correct |
10 ms |
1144 KB |
Output is correct |
49 |
Correct |
9 ms |
1216 KB |
Output is correct |
50 |
Correct |
9 ms |
1228 KB |
Output is correct |
51 |
Correct |
8 ms |
1108 KB |
Output is correct |
52 |
Correct |
9 ms |
1108 KB |
Output is correct |
53 |
Correct |
7 ms |
1100 KB |
Output is correct |
54 |
Correct |
8 ms |
1108 KB |
Output is correct |
55 |
Correct |
7 ms |
1484 KB |
Output is correct |
56 |
Correct |
7 ms |
1484 KB |
Output is correct |
57 |
Correct |
7 ms |
1484 KB |
Output is correct |
58 |
Correct |
6 ms |
1484 KB |
Output is correct |
59 |
Correct |
6 ms |
1484 KB |
Output is correct |
60 |
Correct |
6 ms |
1484 KB |
Output is correct |
61 |
Correct |
6 ms |
1484 KB |
Output is correct |
62 |
Correct |
241 ms |
55388 KB |
Output is correct |
63 |
Correct |
300 ms |
34100 KB |
Output is correct |
64 |
Correct |
347 ms |
32704 KB |
Output is correct |
65 |
Correct |
698 ms |
32716 KB |
Output is correct |
66 |
Correct |
508 ms |
32720 KB |
Output is correct |
67 |
Correct |
649 ms |
32712 KB |
Output is correct |
68 |
Correct |
310 ms |
32444 KB |
Output is correct |
69 |
Correct |
287 ms |
55368 KB |
Output is correct |
70 |
Correct |
324 ms |
32700 KB |
Output is correct |
71 |
Correct |
316 ms |
43360 KB |
Output is correct |
72 |
Correct |
449 ms |
32712 KB |
Output is correct |
73 |
Correct |
507 ms |
32828 KB |
Output is correct |
74 |
Correct |
522 ms |
32700 KB |
Output is correct |
75 |
Correct |
696 ms |
32704 KB |
Output is correct |
76 |
Correct |
254 ms |
55472 KB |
Output is correct |
77 |
Correct |
355 ms |
55432 KB |
Output is correct |
78 |
Correct |
458 ms |
55480 KB |
Output is correct |
79 |
Correct |
575 ms |
55484 KB |
Output is correct |
80 |
Correct |
452 ms |
55476 KB |
Output is correct |
81 |
Correct |
530 ms |
55488 KB |
Output is correct |
82 |
Correct |
249 ms |
55452 KB |
Output is correct |
83 |
Correct |
267 ms |
55456 KB |
Output is correct |
84 |
Correct |
263 ms |
55348 KB |
Output is correct |
85 |
Correct |
364 ms |
55268 KB |
Output is correct |
86 |
Correct |
508 ms |
55548 KB |
Output is correct |
87 |
Correct |
424 ms |
55604 KB |
Output is correct |
88 |
Correct |
395 ms |
32720 KB |
Output is correct |
89 |
Correct |
684 ms |
32716 KB |
Output is correct |
90 |
Correct |
533 ms |
37120 KB |
Output is correct |
91 |
Correct |
580 ms |
55444 KB |
Output is correct |
92 |
Correct |
337 ms |
55424 KB |
Output is correct |
93 |
Correct |
534 ms |
55432 KB |
Output is correct |
94 |
Correct |
593 ms |
55412 KB |
Output is correct |
95 |
Correct |
595 ms |
32700 KB |
Output is correct |
96 |
Correct |
641 ms |
34228 KB |
Output is correct |
97 |
Correct |
738 ms |
38800 KB |
Output is correct |
98 |
Correct |
596 ms |
55596 KB |
Output is correct |
99 |
Correct |
555 ms |
55424 KB |
Output is correct |
100 |
Correct |
579 ms |
55496 KB |
Output is correct |
101 |
Correct |
324 ms |
32700 KB |
Output is correct |
102 |
Correct |
356 ms |
32620 KB |
Output is correct |
103 |
Correct |
434 ms |
32712 KB |
Output is correct |
104 |
Correct |
454 ms |
32704 KB |
Output is correct |
105 |
Correct |
536 ms |
37948 KB |
Output is correct |
106 |
Correct |
360 ms |
55368 KB |
Output is correct |
107 |
Correct |
377 ms |
55412 KB |
Output is correct |
108 |
Correct |
531 ms |
55452 KB |
Output is correct |
109 |
Correct |
496 ms |
32700 KB |
Output is correct |
110 |
Correct |
564 ms |
46096 KB |
Output is correct |
111 |
Correct |
561 ms |
50692 KB |
Output is correct |
112 |
Correct |
416 ms |
50172 KB |
Output is correct |
113 |
Correct |
512 ms |
55512 KB |
Output is correct |
114 |
Correct |
560 ms |
55492 KB |
Output is correct |
115 |
Correct |
261 ms |
55480 KB |
Output is correct |
116 |
Correct |
255 ms |
55460 KB |
Output is correct |
117 |
Correct |
291 ms |
55452 KB |
Output is correct |
118 |
Correct |
302 ms |
55416 KB |
Output is correct |
119 |
Correct |
390 ms |
55504 KB |
Output is correct |
120 |
Correct |
384 ms |
55420 KB |
Output is correct |