// 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 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;
}
memset(lz, -1, sizeof lz);
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);
}
cout << mx[1] << '\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 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:70:5: note: in expansion of macro 'MLR'
70 | 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:86:5: note: in expansion of macro 'MLR'
86 | 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:101:5: note: in expansion of macro 'MLR'
101 | 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:114:5: note: in expansion of macro 'MLR'
114 | MLR;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Execution timed out |
4062 ms |
4948 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Execution timed out |
4062 ms |
4948 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Execution timed out |
4062 ms |
4948 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
44 ms |
11552 KB |
Output is correct |
2 |
Execution timed out |
4065 ms |
11152 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
11904 KB |
Output is correct |
2 |
Correct |
120 ms |
11468 KB |
Output is correct |
3 |
Correct |
210 ms |
11680 KB |
Output is correct |
4 |
Correct |
370 ms |
28012 KB |
Output is correct |
5 |
Correct |
355 ms |
28096 KB |
Output is correct |
6 |
Correct |
377 ms |
28016 KB |
Output is correct |
7 |
Correct |
223 ms |
27908 KB |
Output is correct |
8 |
Correct |
207 ms |
27928 KB |
Output is correct |
9 |
Correct |
228 ms |
27968 KB |
Output is correct |
10 |
Correct |
295 ms |
28048 KB |
Output is correct |
11 |
Correct |
377 ms |
28032 KB |
Output is correct |
12 |
Correct |
339 ms |
28008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
2 ms |
4948 KB |
Output is correct |
3 |
Correct |
3 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4940 KB |
Output is correct |
5 |
Correct |
2 ms |
4948 KB |
Output is correct |
6 |
Correct |
3 ms |
4948 KB |
Output is correct |
7 |
Correct |
2 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
3 ms |
4948 KB |
Output is correct |
10 |
Execution timed out |
4062 ms |
4948 KB |
Time limit exceeded |
11 |
Halted |
0 ms |
0 KB |
- |