#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define dbg(...) 42
#endif
vector<int> a, st, lz;
void build(int id, int tl, int tr) {
if (tl == tr) {
st[id] = a[tl];
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
build(x, tl, tm);
build(y, tm + 1, tr);
st[id] = st[x] + st[y];
}
void update(int id, int tl, int tr, int l, int r, int v) {
if (r < tl || tr < l) return;
if (l <= tl && tr <= r) {
st[id] += v;
lz[id] += v;
return;
}
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
update(x, tl, tm, l, r, v);
update(y, tm + 1, tr, l, r, v);
st[id] = st[x] + st[y] + lz[id];
}
int query(int id, int tl, int tr, int i) {
if (tl == tr) return st[id];
int x = (id << 1) + 1, y = x + 1, tm = (tl + tr) >> 1;
if (i <= tm) {
return query(x, tl, tm, i) + lz[id];
}
else {
return query(y, tm + 1, tr, i) + lz[id];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, x;
cin >> n >> x;
a.resize(n);
st.resize(4 * n);
lz.resize(4 * n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
build(0, 0, n - 1);
auto lis = [&]() {
set<int> s;
for (int i = 0; i < n; i++) {
int x = query(0, 0, n - 1, i);
auto it = s.lower_bound(x);
if (it != s.end()) {
s.erase(it);
}
s.insert(x);
}
return (int)s.size();
};
if (x == 0) {
cout << lis() << '\n';
return 0;
}
int res = 0;
for (int l = 0; l < n; l++) {
for (int r = l; r < n; r++) {
update(0, 0, n - 1, l, r, -x);
res = max(res, lis());
update(0, 0, n - 1, l, r, x);
}
}
cout << res << '\n';
return 0;
}
# | 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... |