#include <bits/stdc++.h>
#define INF 1e9+5
using namespace std;
const int maxN = 1e5+5;
int a[maxN];
int b[maxN];
int f[maxN]; //f[i] = longest decreasing subsequence of b that ends on N+1-i
int g[maxN]; //g[i] = longest increasing subsequence of a that ends on i
int N,d;
void testIO(){
freopen("../test.in","r",stdin);
return;
}
//Max Sparse Segment Tree
int tree[maxN<<6];
int lc[maxN<<6];
int rc[maxN<<6];
int cnt;
void init(){
memset(tree,0,sizeof(tree));
memset(lc,0,sizeof(lc));
memset(rc,0,sizeof(rc));
cnt = 1;
tree[cnt] = lc[cnt] = rc[cnt] = 0;
return;
}
int build(){
tree[++cnt] = 0;
lc[cnt] = 0;
rc[cnt] = 0;
return cnt;
}
void pushup(int p) {
tree[p] = max(tree[lc[p]], tree[rc[p]]);
return;
}
void update(int p, int l, int r, int a, int b, int val){
if(a > r || b < l)return;
if(a <= l && r <= b){
tree[p] = val;
return;
}
if(lc[p] == 0)lc[p] = build();
if(rc[p] == 0)rc[p] = build();
int mid = (l+r)>>1;
update(lc[p],l,mid,a,b,val);
update(rc[p],mid+1,r,a,b,val);
pushup(p);
return;
}
int query(int p, int l, int r, int a, int b){
if(a > r || b < l)return 0;
if(a <= l && r <= b)return tree[p];
int mid = (l+r)>>1;
return max(query(lc[p],l,mid,a,b),query(rc[p],mid+1,r,a,b));
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//testIO();
cin >> N >> d;
for(int i = 1; i <= N; ++i)cin >> a[i]; a[0] = -INF; a[N+1] = INF;
for(int i = 1; i <= N; ++i)b[i] = a[N+1-i]; b[0] = INF;
init();
for(int i = 1; i <= N; ++i){
f[i] = max(f[i], query(1,0,INF,b[i]+1,INF) + 1);
update(1,0,INF,b[i],b[i],f[i]);
}
init();
for(int i = 1; i <= N; ++i){
g[i] = max(g[i], query(1,0,INF,0,a[i]-1) + 1);
update(1,0,INF,a[i],a[i],g[i]);
}
int res = 0;
for(int i = 1; i <= N+1; ++i){
if(a[i-1] - d < a[i])res = max(res, g[i-1] + f[N+1-i]);
}
cout << res << '\n';
return 0;
}
Compilation message
glo.cpp: In function 'int main()':
glo.cpp:73:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
73 | for(int i = 1; i <= N; ++i)cin >> a[i]; a[0] = -INF; a[N+1] = INF;
| ^~~
glo.cpp:73:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
73 | for(int i = 1; i <= N; ++i)cin >> a[i]; a[0] = -INF; a[N+1] = INF;
| ^
glo.cpp:74:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
74 | for(int i = 1; i <= N; ++i)b[i] = a[N+1-i]; b[0] = INF;
| ^~~
glo.cpp:74:49: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
74 | for(int i = 1; i <= N; ++i)b[i] = a[N+1-i]; b[0] = INF;
| ^
glo.cpp: In function 'void testIO()':
glo.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
14 | freopen("../test.in","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
75588 KB |
Output is correct |
2 |
Correct |
44 ms |
75452 KB |
Output is correct |
3 |
Correct |
45 ms |
75464 KB |
Output is correct |
4 |
Correct |
45 ms |
75484 KB |
Output is correct |
5 |
Correct |
43 ms |
75432 KB |
Output is correct |
6 |
Correct |
43 ms |
75356 KB |
Output is correct |
7 |
Correct |
44 ms |
75520 KB |
Output is correct |
8 |
Correct |
43 ms |
75428 KB |
Output is correct |
9 |
Correct |
43 ms |
75484 KB |
Output is correct |
10 |
Correct |
43 ms |
75384 KB |
Output is correct |
11 |
Correct |
42 ms |
75348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
75588 KB |
Output is correct |
2 |
Correct |
44 ms |
75452 KB |
Output is correct |
3 |
Correct |
45 ms |
75464 KB |
Output is correct |
4 |
Correct |
45 ms |
75484 KB |
Output is correct |
5 |
Correct |
43 ms |
75432 KB |
Output is correct |
6 |
Correct |
43 ms |
75356 KB |
Output is correct |
7 |
Correct |
44 ms |
75520 KB |
Output is correct |
8 |
Correct |
43 ms |
75428 KB |
Output is correct |
9 |
Correct |
43 ms |
75484 KB |
Output is correct |
10 |
Correct |
43 ms |
75384 KB |
Output is correct |
11 |
Correct |
42 ms |
75348 KB |
Output is correct |
12 |
Correct |
44 ms |
75460 KB |
Output is correct |
13 |
Correct |
42 ms |
75484 KB |
Output is correct |
14 |
Correct |
43 ms |
75436 KB |
Output is correct |
15 |
Correct |
43 ms |
75412 KB |
Output is correct |
16 |
Correct |
43 ms |
75400 KB |
Output is correct |
17 |
Correct |
43 ms |
75460 KB |
Output is correct |
18 |
Correct |
43 ms |
75428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
75588 KB |
Output is correct |
2 |
Correct |
44 ms |
75452 KB |
Output is correct |
3 |
Correct |
45 ms |
75464 KB |
Output is correct |
4 |
Correct |
45 ms |
75484 KB |
Output is correct |
5 |
Correct |
43 ms |
75432 KB |
Output is correct |
6 |
Correct |
43 ms |
75356 KB |
Output is correct |
7 |
Correct |
44 ms |
75520 KB |
Output is correct |
8 |
Correct |
43 ms |
75428 KB |
Output is correct |
9 |
Correct |
43 ms |
75484 KB |
Output is correct |
10 |
Correct |
43 ms |
75384 KB |
Output is correct |
11 |
Correct |
42 ms |
75348 KB |
Output is correct |
12 |
Correct |
44 ms |
75460 KB |
Output is correct |
13 |
Correct |
42 ms |
75484 KB |
Output is correct |
14 |
Correct |
43 ms |
75436 KB |
Output is correct |
15 |
Correct |
43 ms |
75412 KB |
Output is correct |
16 |
Correct |
43 ms |
75400 KB |
Output is correct |
17 |
Correct |
43 ms |
75460 KB |
Output is correct |
18 |
Correct |
43 ms |
75428 KB |
Output is correct |
19 |
Correct |
45 ms |
75496 KB |
Output is correct |
20 |
Incorrect |
45 ms |
75484 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
16 ms |
1188 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
180 ms |
76332 KB |
Output is correct |
2 |
Correct |
177 ms |
76648 KB |
Output is correct |
3 |
Correct |
172 ms |
76612 KB |
Output is correct |
4 |
Incorrect |
133 ms |
76532 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
323 ms |
77012 KB |
Output is correct |
2 |
Incorrect |
320 ms |
78004 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
47 ms |
75588 KB |
Output is correct |
2 |
Correct |
44 ms |
75452 KB |
Output is correct |
3 |
Correct |
45 ms |
75464 KB |
Output is correct |
4 |
Correct |
45 ms |
75484 KB |
Output is correct |
5 |
Correct |
43 ms |
75432 KB |
Output is correct |
6 |
Correct |
43 ms |
75356 KB |
Output is correct |
7 |
Correct |
44 ms |
75520 KB |
Output is correct |
8 |
Correct |
43 ms |
75428 KB |
Output is correct |
9 |
Correct |
43 ms |
75484 KB |
Output is correct |
10 |
Correct |
43 ms |
75384 KB |
Output is correct |
11 |
Correct |
42 ms |
75348 KB |
Output is correct |
12 |
Correct |
44 ms |
75460 KB |
Output is correct |
13 |
Correct |
42 ms |
75484 KB |
Output is correct |
14 |
Correct |
43 ms |
75436 KB |
Output is correct |
15 |
Correct |
43 ms |
75412 KB |
Output is correct |
16 |
Correct |
43 ms |
75400 KB |
Output is correct |
17 |
Correct |
43 ms |
75460 KB |
Output is correct |
18 |
Correct |
43 ms |
75428 KB |
Output is correct |
19 |
Correct |
45 ms |
75496 KB |
Output is correct |
20 |
Incorrect |
45 ms |
75484 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |