#include <bits/stdc++.h>
using namespace std;
#define ll long long
void test_case() {
int n,x;
cin >> n>>x;
int a[n];
for(int i = 0; i < n; i++) {
cin>>a[i];
}
int a1[n];
a1[0] = 0;
if(x==0) {
vector<int> v;
v.push_back(a[0]);
for(int i = 1; i < n; i++) {
int l =0, r = v.size();
while(l<=r) {
int m = (l+r)/2;
if(v[m]>=a[i]) {
r= m-1;
}
else {
l = m+1;
}
}
if(l>=v.size()) v.push_back(a[i]);
else v[l] = a[i];
}
cout << v.size();
return;
}
vector<int> v;
v.push_back(a[0]);
//------------------------------
for(int i = 1; i < n; i++) {
int l =0, r = v.size();
while(l<=r) {
int m = (l+r)/2;
if(v[m]>=a[i]) {
r= m-1;
}
else {
l = m+1;
}
}
if(l>=v.size()) v.push_back(a[i]);
else v[l] = a[i];
a1[i] = v.size();
}
int a2[n] ;
a2[n-1] = 0;
for(int i = n-2; i >= 0; i--) {
int l =0, r = v.size();
while(l<=r) {
int m = (l+r)/2;
if(v[m]<=a[i]) {
l= m+1;
}
else {
r = m-1;
}
}
if(l>=v.size()) v.push_back(a[i]);
else v[l] = a[i];
a2[i] = v.size();
}
//------------------------------
int ans = 0;
for(int i = 0; i < n; i++) {
ans = max(ans, a2[i]-a1[i]);
}
cout << ans;
}
int main() {
int t;
t=1;
while (t--) test_case();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |