Submission #1229571

#TimeUsernameProblemLanguageResultExecution timeMemory
1229571chikien2009Global Warming (CEOI18_glo)C++20
17 / 100
182 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)); } } st; int n, m, x, a[200002], b[200002], res, c; 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); if (pre[i].first == pre[i - 1].first) { pre[i].second = min(pre[i - 1].second, b[a[i] - 1]); } else if (pre[i].first < pre[i - 1].first) { pre[i] = pre[i - 1]; } else { pre[i].second = b[a[i] - 1]; } } res = pre[n].first; st.Clear(); for (int i = n; i >= 2; --i) { suf[i].first = st.GetVal(1, 1, 2e5, a[i] + 1, 2e5) + 1; st.Set(1, 1, 2e5, a[i], suf[i].first); c = b[a[i - 1] - 1] - x + 1; c = lower_bound(b, b + m, c) - b + 1; res = max(res, pre[i - 1].first + st.GetVal(1, 1, 2e5, c, 2e5)); } 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...