이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define all(d) begin(d), end(d)
using namespace std;
using ll = long long;
struct SegTree {
using T = ll;
T f(T a, T b) { return max(a, b); }
static constexpr T UNIT = 0;
vector<T> s; ll n;
SegTree(ll len) : s(2 * len, UNIT), n(len) {}
void set(ll pos, T val) {
for (s[pos += n] = val; pos /= 2;)
s[pos] = f(s[pos * 2], s[pos * 2 + 1]);
}
T query(ll lo, ll hi) { // query lo to hi (hi not included)
T ra = UNIT, rb = UNIT;
for (lo += n, hi += n; lo < hi; lo /= 2, hi /= 2) {
if (lo % 2) ra = f(ra, s[lo++]);
if (hi % 2) rb = f(s[--hi], rb);
}
return f(ra, rb);
}
};
int main() {
ll n, d;
cin >> n >> d;
vector<ll> a(n);
for (ll i = 0; i < n; i++)
cin >> a[i];
vector<ll> distinctA = a;
distinctA.push_back(LLONG_MIN);
distinctA.push_back(LLONG_MAX);
sort(all(distinctA));
distinctA.erase(unique(all(distinctA)), distinctA.end());
vector<array<ll, 2>> dp(n);
ll ans = 0;
vector<SegTree> st;
st.emplace_back(distinctA.size());
st.emplace_back(distinctA.size());
for (ll i = n - 1; i >= 0; i--) {
ll lo1 = upper_bound(all(distinctA), a[i]) - distinctA.begin();
for (ll u = 0; u < 2; u++)
dp[i][u] = st[u].query(lo1, distinctA.size()) + 1;
ll lo2 = upper_bound(all(distinctA), a[i] - d) - distinctA.begin();
dp[i][1] = max(dp[i][1], st[0].query(lo2, distinctA.size()) + 1);
for (ll u = 0; u < 2; u++)
st[u].set(lo1 - 1, dp[i][u]);
ans = max(ans, dp[i][1]);
}
cout << ans << "\n";
}
# | 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... |