#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{
if(x!=1e9){
int tanss=-1;
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(tans,tanss);
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(tans,tanss);
}
cout << tanss;
}
else{
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]);
}
cout << tans;
}
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 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 |
3 ms |
508 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
3 ms |
684 KB |
Output is correct |
8 |
Correct |
2 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
684 KB |
Output is correct |
10 |
Correct |
3 ms |
716 KB |
Output is correct |
11 |
Correct |
3 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 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 |
3 ms |
508 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
3 ms |
684 KB |
Output is correct |
8 |
Correct |
2 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
684 KB |
Output is correct |
10 |
Correct |
3 ms |
716 KB |
Output is correct |
11 |
Correct |
3 ms |
716 KB |
Output is correct |
12 |
Correct |
35 ms |
716 KB |
Output is correct |
13 |
Correct |
3 ms |
716 KB |
Output is correct |
14 |
Correct |
95 ms |
716 KB |
Output is correct |
15 |
Correct |
48 ms |
716 KB |
Output is correct |
16 |
Correct |
39 ms |
716 KB |
Output is correct |
17 |
Correct |
3 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 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 |
3 ms |
508 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
3 ms |
684 KB |
Output is correct |
8 |
Correct |
2 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
684 KB |
Output is correct |
10 |
Correct |
3 ms |
716 KB |
Output is correct |
11 |
Correct |
3 ms |
716 KB |
Output is correct |
12 |
Correct |
35 ms |
716 KB |
Output is correct |
13 |
Correct |
3 ms |
716 KB |
Output is correct |
14 |
Correct |
95 ms |
716 KB |
Output is correct |
15 |
Correct |
48 ms |
716 KB |
Output is correct |
16 |
Correct |
39 ms |
716 KB |
Output is correct |
17 |
Correct |
3 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
716 KB |
Output is correct |
19 |
Incorrect |
77 ms |
716 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
48 ms |
3692 KB |
Output is correct |
2 |
Correct |
50 ms |
3704 KB |
Output is correct |
3 |
Correct |
71 ms |
3704 KB |
Output is correct |
4 |
Correct |
69 ms |
3704 KB |
Output is correct |
5 |
Correct |
36 ms |
3704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
2053 ms |
3704 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
3704 KB |
Output is correct |
2 |
Correct |
28 ms |
3704 KB |
Output is correct |
3 |
Correct |
63 ms |
3792 KB |
Output is correct |
4 |
Correct |
40 ms |
5748 KB |
Output is correct |
5 |
Correct |
20 ms |
5748 KB |
Output is correct |
6 |
Correct |
30 ms |
5748 KB |
Output is correct |
7 |
Correct |
43 ms |
5748 KB |
Output is correct |
8 |
Correct |
32 ms |
5748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
376 KB |
Output is correct |
2 |
Correct |
2 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 |
3 ms |
508 KB |
Output is correct |
6 |
Correct |
2 ms |
584 KB |
Output is correct |
7 |
Correct |
3 ms |
684 KB |
Output is correct |
8 |
Correct |
2 ms |
684 KB |
Output is correct |
9 |
Correct |
3 ms |
684 KB |
Output is correct |
10 |
Correct |
3 ms |
716 KB |
Output is correct |
11 |
Correct |
3 ms |
716 KB |
Output is correct |
12 |
Correct |
35 ms |
716 KB |
Output is correct |
13 |
Correct |
3 ms |
716 KB |
Output is correct |
14 |
Correct |
95 ms |
716 KB |
Output is correct |
15 |
Correct |
48 ms |
716 KB |
Output is correct |
16 |
Correct |
39 ms |
716 KB |
Output is correct |
17 |
Correct |
3 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
716 KB |
Output is correct |
19 |
Incorrect |
77 ms |
716 KB |
Output isn't correct |
20 |
Halted |
0 ms |
0 KB |
- |