#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pi> vpi;
typedef vector<vi> vvi;
const int inf = 0x3f3f3f3f;
const ll linf = 123456789012345678;
const ll mod = 1000000007;
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl
#define sz(x) ((int)(x).size())
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
ll n, x;
cin >> n >> x;
vl a(n);
for(int i = 0; i < n; i++) cin >> a[i];
vl b(200010, linf);
stack<pair<ll,ll>> undo;
for(int i = n-1; i >= 0; i--){
int p = lower_bound(all(b), -a[i]-x) - b.begin();
undo.emplace(p, b[p]);
b[p] = -a[i]-x;
}
vl c(200010, linf);
int len = 0;
int ans = 0;
for(int i = 0; i < n; i++){
b[undo.top().first] = undo.top().second;
undo.pop();
int p = lower_bound(all(c), a[i]) - c.begin();
if(c[p] == linf) len++;
if(c[p+1] == linf){
assert(p+1 == len);
ans = max(ans, len + (int)(lower_bound(all(b), -a[i]) - b.begin()));
}
c[p] = a[i];
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
4 ms |
3448 KB |
Output is correct |
11 |
Correct |
15 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
4 ms |
3448 KB |
Output is correct |
11 |
Correct |
15 ms |
3448 KB |
Output is correct |
12 |
Correct |
4 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
5 ms |
3448 KB |
Output is correct |
16 |
Correct |
4 ms |
3452 KB |
Output is correct |
17 |
Correct |
4 ms |
3448 KB |
Output is correct |
18 |
Correct |
4 ms |
3448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
4 ms |
3448 KB |
Output is correct |
11 |
Correct |
15 ms |
3448 KB |
Output is correct |
12 |
Correct |
4 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
5 ms |
3448 KB |
Output is correct |
16 |
Correct |
4 ms |
3452 KB |
Output is correct |
17 |
Correct |
4 ms |
3448 KB |
Output is correct |
18 |
Correct |
4 ms |
3448 KB |
Output is correct |
19 |
Correct |
5 ms |
3448 KB |
Output is correct |
20 |
Incorrect |
5 ms |
3448 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
67 ms |
8568 KB |
Output is correct |
2 |
Correct |
68 ms |
8668 KB |
Output is correct |
3 |
Correct |
69 ms |
8696 KB |
Output is correct |
4 |
Correct |
68 ms |
8568 KB |
Output is correct |
5 |
Correct |
58 ms |
8568 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
4952 KB |
Output is correct |
2 |
Correct |
20 ms |
4984 KB |
Output is correct |
3 |
Correct |
20 ms |
4984 KB |
Output is correct |
4 |
Correct |
18 ms |
4984 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
20 ms |
4984 KB |
Output is correct |
7 |
Correct |
18 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
6264 KB |
Output is correct |
2 |
Correct |
37 ms |
6264 KB |
Output is correct |
3 |
Correct |
68 ms |
8540 KB |
Output is correct |
4 |
Correct |
58 ms |
8572 KB |
Output is correct |
5 |
Correct |
35 ms |
6136 KB |
Output is correct |
6 |
Correct |
53 ms |
8312 KB |
Output is correct |
7 |
Correct |
68 ms |
8284 KB |
Output is correct |
8 |
Correct |
31 ms |
6136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3448 KB |
Output is correct |
2 |
Correct |
5 ms |
3448 KB |
Output is correct |
3 |
Correct |
5 ms |
3448 KB |
Output is correct |
4 |
Correct |
5 ms |
3448 KB |
Output is correct |
5 |
Correct |
5 ms |
3448 KB |
Output is correct |
6 |
Correct |
5 ms |
3576 KB |
Output is correct |
7 |
Correct |
5 ms |
3448 KB |
Output is correct |
8 |
Correct |
5 ms |
3448 KB |
Output is correct |
9 |
Correct |
5 ms |
3448 KB |
Output is correct |
10 |
Correct |
4 ms |
3448 KB |
Output is correct |
11 |
Correct |
15 ms |
3448 KB |
Output is correct |
12 |
Correct |
4 ms |
3448 KB |
Output is correct |
13 |
Correct |
4 ms |
3448 KB |
Output is correct |
14 |
Correct |
4 ms |
3448 KB |
Output is correct |
15 |
Correct |
5 ms |
3448 KB |
Output is correct |
16 |
Correct |
4 ms |
3452 KB |
Output is correct |
17 |
Correct |
4 ms |
3448 KB |
Output is correct |
18 |
Correct |
4 ms |
3448 KB |
Output is correct |
19 |
Correct |
5 ms |
3448 KB |
Output is correct |
20 |
Incorrect |
5 ms |
3448 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |