#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
struct lis{
set<pii> s;
void add(pii nw){
s.insert(nw);
auto it = s.lower_bound(nw);
if(it != s.begin()){
auto it2 = it;
--it2;
if(it2->ss >= it->ss){
s.erase(it);
return;
}
}
++it;
while(it != s.end()){
if(it->ss <= nw.ss)
it = s.erase(it);
else
break;
}
}
int get(int x){
auto it = s.lower_bound({x, 0});
if(it == s.begin())
return 0;
--it;
return it->ss;
}
};
lis s1, s2;
int n, x;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n >> x;
int ans = 0;
while(n--){
int a;
cin >> a;
int val = s1.get(a);
ans = max(ans, val+1);
s1.add({a, val+1});
val = s1.get(a+x);
ans = max(ans, val+1);
s2.add({a, val+1});
val = s2.get(a);
ans = max(ans, val+1);
s2.add({a, val+1});
}
cout << ans << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
202 ms |
2384 KB |
Output is correct |
2 |
Correct |
191 ms |
2240 KB |
Output is correct |
3 |
Correct |
196 ms |
2284 KB |
Output is correct |
4 |
Correct |
198 ms |
2272 KB |
Output is correct |
5 |
Correct |
216 ms |
10820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
44 ms |
716 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
87 ms |
1196 KB |
Output is correct |
2 |
Correct |
86 ms |
1300 KB |
Output is correct |
3 |
Correct |
180 ms |
2248 KB |
Output is correct |
4 |
Correct |
159 ms |
7692 KB |
Output is correct |
5 |
Correct |
136 ms |
5444 KB |
Output is correct |
6 |
Correct |
206 ms |
10392 KB |
Output is correct |
7 |
Correct |
181 ms |
11036 KB |
Output is correct |
8 |
Correct |
69 ms |
1204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |