Submission #1229545

#TimeUsernameProblemLanguageResultExecution timeMemory
1229545chikien2009Global Warming (CEOI18_glo)C++20
62 / 100
139 ms8264 KiB
#include <bits/stdc++.h> using namespace std; void setup() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); } struct SEGMENT_TREE { int tree[800000]; inline void Clear() { fill_n(tree, 8e5, 0); } inline void Set(int ind, int l, int r, int x, int v) { if (r < x || x < l) { return; } if (l == r) { tree[ind] = max(tree[ind], v); return; } int m = (l + r) >> 1; Set(ind << 1, l, m, x, v); Set(ind << 1 | 1, m + 1, r, x, v); tree[ind] = max(tree[ind << 1], tree[ind << 1 | 1]); } inline int GetVal(int ind, int l, int r, int x, int y) { if (r < x || y < l || y < x) { return 0; } if (x <= l && r <= y) { return tree[ind]; } int m = (l + r) >> 1; return max(GetVal(ind << 1, l, m, x, y), GetVal(ind << 1 | 1, m + 1, r, x, y)); } inline int GetMin(int ind, int l, int r, int v) { if (l == r) { return l; } int m = (l + r) >> 1; if (tree[ind << 1] == v) { return GetMin(ind << 1, l, m, v); } return GetMin(ind << 1 | 1, m + 1, r, v); } inline int GetMax(int ind, int l, int r, int v) { if (l == r) { return l; } int m = (l + r) >> 1; if (tree[ind << 1 | 1] == v) { return GetMin(ind << 1 | 1, m + 1, r, v); } return GetMax(ind << 1, l, m, v); } } st; int n, m, x, a[200002], b[200002], res; pair<int, int> pre[200002], suf[200002]; int main() { setup(); cin >> n >> x; for (int i = 1; i <= n; ++i) { cin >> a[i]; b[i - 1] = a[i]; } sort(b, b + n); m = unique(b, b + n) - b; for (int i = 1; i <= n; ++i) { a[i] = lower_bound(b, b + m, a[i]) - b + 1; } for (int i = 1; i <= n; ++i) { pre[i].first = st.GetVal(1, 1, 2e5, 1, a[i] - 1) + 1; st.Set(1, 1, 2e5, a[i], pre[i].first); pre[i].first = max(pre[i - 1].first, pre[i].first); pre[i].second = st.GetMin(1, 1, 2e5, pre[i].first); } res = pre[n].first; st.Clear(); for (int i = n; i >= 1; --i) { suf[i].first = st.GetVal(1, 1, 2e5, a[i] + 1, 2e5) + 1; st.Set(1, 1, 2e5, a[i], suf[i].first); suf[i].first = max(suf[i + 1].first, suf[i].first); suf[i].second = st.GetMax(1, 1, 2e5, suf[i].first); } for (int i = 2; i <= n; ++i) { if (b[pre[i - 1].second - 1] - x < b[suf[i].second - 1]) { res = max(res, pre[i - 1].first + suf[i].first); } } cout << res; 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...