#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;
}
vl A;
int dp[100000];
int LIS2(int pos){
if(dp[pos] != -1) return dp[pos];
int r = 0;
for(int i = pos+1; i < sz(A); i++){
if(A[i] > A[pos])
r = max(r, LIS2(i));
}
return dp[pos] = r + 1;
}
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(1){
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 |
5112 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 |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5116 KB |
Output is correct |
9 |
Correct |
19 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5080 KB |
Output is correct |
11 |
Correct |
8 ms |
5112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 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 |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5116 KB |
Output is correct |
9 |
Correct |
19 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5080 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 |
5112 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
13 ms |
5208 KB |
Output is correct |
16 |
Correct |
12 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5080 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 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 |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5116 KB |
Output is correct |
9 |
Correct |
19 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5080 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 |
5112 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
13 ms |
5208 KB |
Output is correct |
16 |
Correct |
12 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5080 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
19 |
Correct |
167 ms |
5240 KB |
Output is correct |
20 |
Correct |
166 ms |
5152 KB |
Output is correct |
21 |
Correct |
173 ms |
5084 KB |
Output is correct |
22 |
Correct |
164 ms |
5112 KB |
Output is correct |
23 |
Correct |
168 ms |
5112 KB |
Output is correct |
24 |
Correct |
167 ms |
5180 KB |
Output is correct |
25 |
Correct |
150 ms |
5120 KB |
Output is correct |
26 |
Correct |
170 ms |
5120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2057 ms |
8752 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2055 ms |
6040 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2056 ms |
6828 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 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 |
5112 KB |
Output is correct |
7 |
Correct |
7 ms |
5112 KB |
Output is correct |
8 |
Correct |
7 ms |
5116 KB |
Output is correct |
9 |
Correct |
19 ms |
5112 KB |
Output is correct |
10 |
Correct |
7 ms |
5080 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 |
5112 KB |
Output is correct |
14 |
Correct |
12 ms |
5112 KB |
Output is correct |
15 |
Correct |
13 ms |
5208 KB |
Output is correct |
16 |
Correct |
12 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5080 KB |
Output is correct |
18 |
Correct |
9 ms |
5084 KB |
Output is correct |
19 |
Correct |
167 ms |
5240 KB |
Output is correct |
20 |
Correct |
166 ms |
5152 KB |
Output is correct |
21 |
Correct |
173 ms |
5084 KB |
Output is correct |
22 |
Correct |
164 ms |
5112 KB |
Output is correct |
23 |
Correct |
168 ms |
5112 KB |
Output is correct |
24 |
Correct |
167 ms |
5180 KB |
Output is correct |
25 |
Correct |
150 ms |
5120 KB |
Output is correct |
26 |
Correct |
170 ms |
5120 KB |
Output is correct |
27 |
Execution timed out |
2057 ms |
8752 KB |
Time limit exceeded |
28 |
Halted |
0 ms |
0 KB |
- |