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>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp(x, y) make_pair(x, y)
#define sz(v) ((int) (v).size())
#define all(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define BIT(x, y) (((x) >> (y)) & 1)
#define pb push_back
#define heap priority_queue
#define max_rng *max_element
#define min_rng *min_element
#define rep(i, n) for(int i = 1, _n = (n); i <= _n; ++i)
#define forn(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define ford(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
template <class X, class Y>
inline bool maximize(X &x, Y y) {
return (x < y ? x = y, true : false);
}
template <class X, class Y>
inline bool minimize(X &x, Y y) {
return (x > y ? x = y, true : false);
}
template <class X>
inline void compress(X &a) {
sort(all(a));
a.resize(unique(all(a)) - a.begin());
}
int ctz(ll x) { return __builtin_ctzll(x); }
int lg(ll x) { return 63 - __builtin_clzll(x); }
int popcount(ll x) { return __builtin_popcount(x); }
const ll oo = (ll) 1e17;
const int INF = (int) 1e9 + 7, MOD = (int) 1e9 + 7;
const int N = 2e5 + 15;
void add(int &x, int y) { x += y; if (x >= MOD) x -= MOD; }
void sub(int &x, int y) { x -= y; if (x < 0) x += MOD; }
int n;
ll x, a[N], ID[N][3];
struct Seg {
int n;
vector<ll> st;
Seg(int n) : n(n) {
st.resize(2 * n + 5);
}
void upd(int p, ll d) {
p += n;
maximize(st[p], d);
while (p > 1) {
p >>= 1;
st[p] = max(st[2 * p], st[2 * p + 1]);
}
}
ll query(int l, int r) {
l += n;
r += n + 1;
ll ans = 0;
for (; l < r; l >>= 1, r >>= 1) {
if (l & 1) maximize(ans, st[l++]);
if (r & 1) maximize(ans, st[--r]);
}
return ans;
}
void reset() { st.assign(2 * n + 5, 0); }
};
int main(void) {
// think what before starting to code
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> x;
forn(i, 1, n) cin >> a[i];
vector<ll> cps;
forn(i, 1, n) forn(j, -1, 1) {
cps.pb(a[i] + j * x);
}
compress(cps);
forn(i, 1, n) forn(j, 0, 2) {
ID[i][j] = lower_bound(all(cps), a[i] + (j - 1) * x) - cps.begin() + 1;
}
int m = sz(cps);
Seg s(m);
vector<ll> pf(n + 1, 0), sf(n + 1, 0);
forn(i, 1, n) {
pf[i] = s.query(1, ID[i][1] - 1) + 1;
s.upd(ID[i][1], pf[i]);
}
s.reset();
ford(i, n, 1) {
sf[i] = s.query(ID[i][1] + 1, m) + 1;
s.upd(ID[i][1], sf[i]);
}
s.reset();
ll ans = 0;
forn(i, 1, n) {
maximize(ans, sf[i] + s.query(1, ID[i][2] - 1));
s.upd(ID[i][1], pf[i]);
}
cout << ans;
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... |