// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 300005;
int n, d;
int a[MAXN];
vii dct;
int ans;
#define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
int ptr;
ii mn[MAXN * 4];
int lz[MAXN * 4], onc[MAXN * 4];
void propo(int u, int lo, int hi) {
if (lz[u] == -1) {
return;
}
MLR;
mn[lc] = {lz[u], lo};
mn[rc] = {lz[u], mid + 1};
lz[lc] = lz[u];
lz[rc] = lz[u];
lz[u] = -1;
}
void init(int u = 1, int lo = 0, int hi = ptr) {
lz[u] = -1;
mn[u] = {INF, lo};
if (lo != hi) {
MLR;
init(lc, lo, mid);
init(rc, mid + 1, hi);
}
}
void updt(int s, int e, int x, int u = 1, int lo = 0, int hi = ptr) {
if (lo >= s && hi <= e) {
if (onc[u] == 0) {
x = INF;
}
mn[u] = {x, lo};
lz[u] = x;
return;
}
propo(u, lo, hi);
MLR;
if (s <= mid) {
updt(s, e, x, lc, lo, mid);
}
if (e > mid) {
updt(s, e, x, rc, mid + 1, hi);
}
mn[u] = min(mn[lc], mn[rc]);
}
void togglet(int p, int x, int u = 1, int lo = 0, int hi = ptr) {
if (lo == hi) {
mn[u] = {x, lo};
onc[u] = x != INF;
return;
}
propo(u, lo, hi);
MLR;
if (p <= mid) {
togglet(p, x, lc, lo, mid);
} else {
togglet(p, x, rc, mid + 1, hi);
}
mn[u] = min(mn[lc], mn[rc]);
onc[u] = onc[lc] + onc[rc];
}
int mx[MAXN * 4];
void updv(int p, int x, int u = 1, int lo = 0, int hi = ptr) {
if (lo == hi) {
mx[u] = x;
return;
}
MLR;
if (p <= mid) {
updv(p, x, lc, lo, mid);
} else {
updv(p, x, rc, mid + 1, hi);
}
mx[u] = max(mx[lc], mx[rc]);
}
int qmx(int s, int e, int u = 1, int lo = 0, int hi = ptr) {
if (lo >= s && hi <= e) {
return mx[u];
}
int res = 0;
MLR;
if (s <= mid) {
mxto(res, qmx(s, e, lc, lo, mid));
}
if (e > mid) {
mxto(res, qmx(s, e, rc, mid + 1, hi));
}
return res;
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> d;
REP (i, 1, n + 1) {
cin >> a[i];
dct.pb({a[i], i});
}
sort(ALL(dct));
int prv = -1; ptr = 0;
for (auto [x, i] : dct) {
if (x != prv) {
ptr++;
prv = x;
}
a[i] = ptr;
}
init();
REP (i, 1, n + 1) {
cerr << i << ' ' << a[i] << '\n';
updt(a[i], ptr, i);
while (i - mn[1].FI > d) {
int id = mn[1].SE;
updv(id, 0);
togglet(id, INF);
}
int v = qmx(0, a[i] - 1) + 1;
int pv = qmx(a[i], a[i]);
cerr << ' ' << pv << ' ' << v << '\n';
updv(a[i], max(pv, v));
togglet(a[i], i);
mxto(ans, mx[1]);
}
cout << ans << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'void propo(int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:53:5: note: in expansion of macro 'MLR'
53 | MLR;
| ^~~
Main.cpp: In function 'void init(int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:64:9: note: in expansion of macro 'MLR'
64 | MLR;
| ^~~
Main.cpp: In function 'void updt(int, int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:79:5: note: in expansion of macro 'MLR'
79 | MLR;
| ^~~
Main.cpp: In function 'void togglet(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:95:5: note: in expansion of macro 'MLR'
95 | MLR;
| ^~~
Main.cpp: In function 'void updv(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:110:5: note: in expansion of macro 'MLR'
110 | MLR;
| ^~~
Main.cpp: In function 'int qmx(int, int, int, int, int)':
Main.cpp:45:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | #define MLR int mid = lo + hi >> 1, lc = u << 1, rc = u << 1 ^ 1
| ~~~^~~~
Main.cpp:123:5: note: in expansion of macro 'MLR'
123 | MLR;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
360 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
464 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
360 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
464 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
360 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
464 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
5580 KB |
Output is correct |
2 |
Correct |
81 ms |
5548 KB |
Output is correct |
3 |
Incorrect |
280 ms |
5580 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
5572 KB |
Output is correct |
2 |
Correct |
113 ms |
5580 KB |
Output is correct |
3 |
Correct |
200 ms |
5580 KB |
Output is correct |
4 |
Correct |
355 ms |
24464 KB |
Output is correct |
5 |
Correct |
304 ms |
24508 KB |
Output is correct |
6 |
Correct |
370 ms |
24396 KB |
Output is correct |
7 |
Correct |
202 ms |
24420 KB |
Output is correct |
8 |
Correct |
200 ms |
24424 KB |
Output is correct |
9 |
Correct |
222 ms |
24376 KB |
Output is correct |
10 |
Correct |
283 ms |
24456 KB |
Output is correct |
11 |
Correct |
355 ms |
24504 KB |
Output is correct |
12 |
Correct |
295 ms |
24508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
2 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
360 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
464 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
0 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Incorrect |
2 ms |
340 KB |
Output isn't correct |
28 |
Halted |
0 ms |
0 KB |
- |