Submission #580416

#TimeUsernameProblemLanguageResultExecution timeMemory
580416tengiz05Global Warming (CEOI18_glo)C++17
100 / 100
390 ms10516 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; template<class Info, class Merge = std::plus<Info>> struct SegmentTree { const int n; const Merge merge; std::vector<Info> info; SegmentTree(int n) : n(n), merge(Merge()), info(4 << std::__lg(n)) {} SegmentTree(std::vector<Info> init) : SegmentTree(init.size()) { std::function<void(int, int, int)> build = [&](int p, int l, int r) { if (r - l == 1) { info[p] = init[l]; return; } int m = (l + r) / 2; build(2 * p, l, m); build(2 * p + 1, m, r); pull(p); }; build(1, 0, n); } void pull(int p) { info[p] = merge(info[2 * p], info[2 * p + 1]); } void modify(int p, int l, int r, int x, const Info &v) { if (r - l == 1) { info[p] = v; return; } int m = (l + r) / 2; if (x < m) { modify(2 * p, l, m, x, v); } else { modify(2 * p + 1, m, r, x, v); } pull(p); } void modify(int p, const Info &v) { modify(1, 0, n, p, v); } Info rangeQuery(int p, int l, int r, int x, int y) { if (l >= y || r <= x) { return Info(); } if (l >= x && r <= y) { return info[p]; } int m = (l + r) / 2; return merge(rangeQuery(2 * p, l, m, x, y), rangeQuery(2 * p + 1, m, r, x, y)); } Info rangeQuery(int l, int r) { return rangeQuery(1, 0, n, l, r); } }; struct Info { int x; Info(int x = 0) : x(x) {} }; Info operator+(const Info &a, const Info &b) { return Info(max(a.x, b.x)); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, X; cin >> n >> X; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> f = a; sort(f.begin(), f.end()); f.erase(unique(f.begin(), f.end()), f.end()); vector<int> b(n); for (int i = 0; i < n; i++) { b[i] = lower_bound(f.begin(), f.end(), a[i]) - f.begin(); } vector<int> dp(n); SegmentTree<Info> s(n); vector<int> changes; for (int i = n - 1; i >= 0; i--) { int x = s.rangeQuery(b[i] + 1, n).x; dp[i] = x + 1; changes.emplace_back(s.rangeQuery(b[i], b[i] + 1).x); s.modify(b[i], Info(dp[i])); } SegmentTree<Info> t(n); int ans = 1; for (int i = 0; i < n; i++) { s.modify(b[i], Info(changes.back())); changes.pop_back(); int x = t.rangeQuery(0, b[i]).x; int p = upper_bound(f.begin(), f.end(), f[b[i]] - X) - f.begin(); ans = max(ans, x + 1 + s.rangeQuery(p, n).x); t.modify(b[i], Info(x + 1)); } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...