#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define ll long long
#define eb emplace_back
#define V vector
const int base=(1<<20);
int n, X;
V<int> A;
map<int, int> ch;
struct SegTree {
int T[2*base];
void update(int v, int x) {
v+=base;
T[v]=max(T[v], x);
v/=2;
while(v>0) {
T[v]=max(T[2*v], T[2*v+1]);
v/=2;
}
}
int query(int a, int b) {
int res=0;
a+=base-1;
b+=base+1;
while(a/2!=b/2) {
if(a%2==0) res=max(res, T[a+1]);
if(b%2==1) res=max(res, T[b-1]);
a/=2; b/=2;
}
return res;
}
} AT, BT;
signed main() {
cin.tie(0) -> ios_base::sync_with_stdio(0);
cin >> n >> X;
A.resize(n+1);
V<int> all;
FOR(i, 1, n) {
cin >> A[i];
all.eb(A[i]);
all.eb(A[i]+X);
}
sort(all.begin(), all.end());
int t=0;
for(int u : all) {
if(ch[u]==0) ch[u]=++t;
}
FOR(i, 1, n) {
int x = A[i];
AT.update(ch[x], AT.query(0, ch[x]-1)+1);
BT.update(ch[x], BT.query(0, ch[x]-1)+1);
BT.update(ch[x], AT.query(0, ch[x+X]-1)+1);
}
cout << max(AT.T[1], BT.T[1]) << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
374 ms |
25900 KB |
Output is correct |
2 |
Correct |
380 ms |
25792 KB |
Output is correct |
3 |
Correct |
428 ms |
25824 KB |
Output is correct |
4 |
Correct |
382 ms |
25792 KB |
Output is correct |
5 |
Correct |
186 ms |
15664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
95 ms |
11468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
224 ms |
19540 KB |
Output is correct |
2 |
Correct |
250 ms |
19400 KB |
Output is correct |
3 |
Correct |
504 ms |
38340 KB |
Output is correct |
4 |
Correct |
231 ms |
22064 KB |
Output is correct |
5 |
Correct |
146 ms |
19184 KB |
Output is correct |
6 |
Correct |
294 ms |
35776 KB |
Output is correct |
7 |
Correct |
282 ms |
36476 KB |
Output is correct |
8 |
Correct |
177 ms |
19392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |