#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
#define INF 1e18
#define ret return
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector < pair<int, int> > vii;
typedef long double ld;
typedef tree<pair<int,int>, null_type, less<pair<int,int> >, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
ll a[222222];
ll b[222222];
int ans1[222222];
int ans2[222222];
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
ll x;
cin >> n >> x;
for(int i = 0; i < n; i++){
cin >> a[i];
}
if(n<=50 && x<=50){
int tans=-1;
for(int l = 0; l < n; l++){
for(int r = l+1; r <= n; r++){
for(int d = -x; d <= x; d++){
for(int i = 0; i < n; i++){
b[i]=a[i];
}
for(int i = l; i < r; i++){
b[i]+=d;
}
vector<ll> dd(n+1,INF);
for(int i = 0; i < n; i++){
*lower_bound(dd.begin(),dd.end(),b[i])=b[i];
}
for(int i = 0; i <= n; i++){
if(dd[i]==INF){
tans=max(tans,i);
i=n+1;
}
}
}
}
}
cout << tans;
ret 0;
}
else if(x==0){
vector<ll> dd(n+1,INF);
for(int i = 0; i < n; i++){
*lower_bound(dd.begin(),dd.end(),a[i])=a[i];
}
for(int i = 0; i <= n; i++){
if(dd[i]==INF){
cout << i;
ret 0;
}
}
}
else{
int tanss=-1;
for(int t = 0; t < n; t++){
a[t]-=x;
vector <ll> LIS;
for(int i = 0; i < n; i++){
if(LIS.empty()){
LIS.pb(a[i]);
}
else{
if(LIS[LIS.size()-1]<a[i]){
LIS.pb(a[i]);
}
else{
*lower_bound(LIS.begin(),LIS.end(),a[i])=a[i];
}
}
ans1[i]=LIS.size();
}
vector <ll> LISS;
for(int i = 0; i < n; i++){
if(LISS.empty()){
LISS.pb(-a[n-1-i]);
}
else{
if(LISS[LISS.size()-1]<-a[n-1-i]){
LISS.pb(-a[n-1-i]);
}
else{
*lower_bound(LISS.begin(),LISS.end(),-a[n-1-i])=-a[n-1-i];
}
}
ans2[n-i-1]=LISS.size();
}
int tans = max(ans2[0],ans1[n-1]);
/*for(int i = 0; i < n; i++){
cout << '*' << ans2[i] << endl;
}*/
for(int i = 0; i < n-1; i++){
tans=max(tans,ans1[i]+ans2[i+1]);
}
tanss=max(tanss,tans);
}
cout << tanss;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Correct |
2 ms |
584 KB |
Output is correct |
| 7 |
Correct |
3 ms |
680 KB |
Output is correct |
| 8 |
Correct |
2 ms |
680 KB |
Output is correct |
| 9 |
Correct |
2 ms |
680 KB |
Output is correct |
| 10 |
Correct |
3 ms |
680 KB |
Output is correct |
| 11 |
Correct |
3 ms |
680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Correct |
2 ms |
584 KB |
Output is correct |
| 7 |
Correct |
3 ms |
680 KB |
Output is correct |
| 8 |
Correct |
2 ms |
680 KB |
Output is correct |
| 9 |
Correct |
2 ms |
680 KB |
Output is correct |
| 10 |
Correct |
3 ms |
680 KB |
Output is correct |
| 11 |
Correct |
3 ms |
680 KB |
Output is correct |
| 12 |
Correct |
29 ms |
680 KB |
Output is correct |
| 13 |
Correct |
3 ms |
680 KB |
Output is correct |
| 14 |
Correct |
116 ms |
748 KB |
Output is correct |
| 15 |
Correct |
43 ms |
748 KB |
Output is correct |
| 16 |
Correct |
39 ms |
748 KB |
Output is correct |
| 17 |
Correct |
2 ms |
748 KB |
Output is correct |
| 18 |
Correct |
3 ms |
748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Correct |
2 ms |
584 KB |
Output is correct |
| 7 |
Correct |
3 ms |
680 KB |
Output is correct |
| 8 |
Correct |
2 ms |
680 KB |
Output is correct |
| 9 |
Correct |
2 ms |
680 KB |
Output is correct |
| 10 |
Correct |
3 ms |
680 KB |
Output is correct |
| 11 |
Correct |
3 ms |
680 KB |
Output is correct |
| 12 |
Correct |
29 ms |
680 KB |
Output is correct |
| 13 |
Correct |
3 ms |
680 KB |
Output is correct |
| 14 |
Correct |
116 ms |
748 KB |
Output is correct |
| 15 |
Correct |
43 ms |
748 KB |
Output is correct |
| 16 |
Correct |
39 ms |
748 KB |
Output is correct |
| 17 |
Correct |
2 ms |
748 KB |
Output is correct |
| 18 |
Correct |
3 ms |
748 KB |
Output is correct |
| 19 |
Incorrect |
84 ms |
748 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
71 ms |
3708 KB |
Output is correct |
| 2 |
Correct |
50 ms |
3708 KB |
Output is correct |
| 3 |
Correct |
56 ms |
3740 KB |
Output is correct |
| 4 |
Correct |
56 ms |
3740 KB |
Output is correct |
| 5 |
Correct |
40 ms |
3740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
3740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2077 ms |
3740 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
432 KB |
Output is correct |
| 4 |
Correct |
2 ms |
508 KB |
Output is correct |
| 5 |
Correct |
2 ms |
584 KB |
Output is correct |
| 6 |
Correct |
2 ms |
584 KB |
Output is correct |
| 7 |
Correct |
3 ms |
680 KB |
Output is correct |
| 8 |
Correct |
2 ms |
680 KB |
Output is correct |
| 9 |
Correct |
2 ms |
680 KB |
Output is correct |
| 10 |
Correct |
3 ms |
680 KB |
Output is correct |
| 11 |
Correct |
3 ms |
680 KB |
Output is correct |
| 12 |
Correct |
29 ms |
680 KB |
Output is correct |
| 13 |
Correct |
3 ms |
680 KB |
Output is correct |
| 14 |
Correct |
116 ms |
748 KB |
Output is correct |
| 15 |
Correct |
43 ms |
748 KB |
Output is correct |
| 16 |
Correct |
39 ms |
748 KB |
Output is correct |
| 17 |
Correct |
2 ms |
748 KB |
Output is correct |
| 18 |
Correct |
3 ms |
748 KB |
Output is correct |
| 19 |
Incorrect |
84 ms |
748 KB |
Output isn't correct |
| 20 |
Halted |
0 ms |
0 KB |
- |
