| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 984558 | Acanikolic | Global Warming (CEOI18_glo) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define F first
#define S second
const int N = 500 + 10;
const int inf = 2e9;
const int mod = 998244353;
using namespace std;
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,x,res = 0;
cin >> n >> x;
vector<int>a(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
a[i] -= x;
}
vector<pair<int,int>>pref(n);
vector<int>v;
for(int i = 0; i < n; i++) {
if(v.empty() || v.back() < a[i]) {
v.pb(a[i]);
}else {
int lb = lower_bound(v.begin(),v.end(),a[i]) - v.begin();
v[lb] = a[i];
}
pref[i] = {v.back(),v.size()};
}
res = pref[n - 1].S;
for(int i = 0; i < n; i++) a[i] += x;
vector<int>vec;
for(int i = n - 1; i > 0; i--) {
if(vec.empty() || vec.back() > a[i]) {
vec.pb(a[i]);
}else {
if(vec[0] < a[i]) {
vec[0] = a[i];
continue;
}
int lb = lower_bound(v.begin(),v.end(),v[i]) - v.begin();
lb -= 1;
vec[lb] = a[i];
}
int l = 0,r = i - 1,ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
if(pref[mid].F < vec.back()) {
ans = mid;
l = mid + 1;
}else {
r = mid - 1;
}
}
res = max(res,vec.size() + (ans != -1 ? pref[ans].S : 0));
}
cout << res;
return 0;
}