#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 LIS(vl a){
vl b(200010, linf);
int r = 0;
for(int i = 0; i < sz(a); i++){
auto p = lower_bound(all(b), a[i]);
if(*p == linf) r++;
*p = a[i];
}
return r;
}
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(p+1 == len){
ans = max(ans, len + (int)(lower_bound(all(b), -a[i]) - b.begin()));
}
c[p] = a[i];
}
if(n <= 1000){
int ans = 0;
for(int i = n-1; i >= 0; i--){
a[i] += x;
ans = max(ans, LIS(a));
}
}
cout << ans << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5080 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5084 KB |
Output is correct |
4 |
Correct |
7 ms |
5080 KB |
Output is correct |
5 |
Correct |
7 ms |
5112 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5080 KB |
Output is correct |
8 |
Correct |
7 ms |
4952 KB |
Output is correct |
9 |
Correct |
8 ms |
5116 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5080 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5084 KB |
Output is correct |
4 |
Correct |
7 ms |
5080 KB |
Output is correct |
5 |
Correct |
7 ms |
5112 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5080 KB |
Output is correct |
8 |
Correct |
7 ms |
4952 KB |
Output is correct |
9 |
Correct |
8 ms |
5116 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
12 ms |
5112 KB |
Output is correct |
13 |
Correct |
12 ms |
5080 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
12 ms |
5112 KB |
Output is correct |
16 |
Correct |
13 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5080 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5084 KB |
Output is correct |
4 |
Correct |
7 ms |
5080 KB |
Output is correct |
5 |
Correct |
7 ms |
5112 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5080 KB |
Output is correct |
8 |
Correct |
7 ms |
4952 KB |
Output is correct |
9 |
Correct |
8 ms |
5116 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
12 ms |
5112 KB |
Output is correct |
13 |
Correct |
12 ms |
5080 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
12 ms |
5112 KB |
Output is correct |
16 |
Correct |
13 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
19 |
Correct |
167 ms |
5112 KB |
Output is correct |
20 |
Incorrect |
169 ms |
5080 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
69 ms |
8876 KB |
Output is correct |
2 |
Correct |
69 ms |
8868 KB |
Output is correct |
3 |
Correct |
68 ms |
8820 KB |
Output is correct |
4 |
Correct |
68 ms |
8824 KB |
Output is correct |
5 |
Correct |
60 ms |
8824 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
5112 KB |
Output is correct |
2 |
Correct |
20 ms |
5112 KB |
Output is correct |
3 |
Correct |
20 ms |
5112 KB |
Output is correct |
4 |
Correct |
18 ms |
4984 KB |
Output is correct |
5 |
Correct |
9 ms |
5112 KB |
Output is correct |
6 |
Correct |
20 ms |
4984 KB |
Output is correct |
7 |
Correct |
18 ms |
5240 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
6392 KB |
Output is correct |
2 |
Correct |
36 ms |
6456 KB |
Output is correct |
3 |
Correct |
71 ms |
8872 KB |
Output is correct |
4 |
Correct |
59 ms |
8860 KB |
Output is correct |
5 |
Correct |
35 ms |
6392 KB |
Output is correct |
6 |
Correct |
52 ms |
8572 KB |
Output is correct |
7 |
Correct |
63 ms |
8652 KB |
Output is correct |
8 |
Correct |
32 ms |
6432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5080 KB |
Output is correct |
2 |
Correct |
7 ms |
5112 KB |
Output is correct |
3 |
Correct |
7 ms |
5084 KB |
Output is correct |
4 |
Correct |
7 ms |
5080 KB |
Output is correct |
5 |
Correct |
7 ms |
5112 KB |
Output is correct |
6 |
Correct |
7 ms |
5080 KB |
Output is correct |
7 |
Correct |
7 ms |
5080 KB |
Output is correct |
8 |
Correct |
7 ms |
4952 KB |
Output is correct |
9 |
Correct |
8 ms |
5116 KB |
Output is correct |
10 |
Correct |
7 ms |
5112 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
12 |
Correct |
12 ms |
5112 KB |
Output is correct |
13 |
Correct |
12 ms |
5080 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
12 ms |
5112 KB |
Output is correct |
16 |
Correct |
13 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
19 |
Correct |
167 ms |
5112 KB |
Output is correct |
20 |
Incorrect |
169 ms |
5080 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |