Submission #501916

#TimeUsernameProblemLanguageResultExecution timeMemory
501916nightyHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
132 ms27708 KiB
#include <bits/stdc++.h> using namespace std; bool canSort(vector<int>& a, int l, int r, int k) { int maxVal = 0; for (int i = l; i <= r; ++i) { if (maxVal > a[i] && maxVal + a[i] > k) { return false; } maxVal = max(maxVal, a[i]); } return true; } int calcMaxInv(vector<int>& a, int l, int r) { int maxVal = 0, res = 0; for (int i = l; i <= r; ++i) { if (maxVal > a[i]) { res = max(res, maxVal + a[i]); } maxVal = max(maxVal, a[i]); } return res; } const int K = 450; set<int> s[K]; int maxInverse[K]; int calcMaxInv2(vector<int>& a, int l, int r) { int res = calcMaxInv(a, l, min(r, l - l % K + K - 1)); int maxVal = *max_element(a.begin() + l, a.begin() + l - l % K + K - 1 + 1); l = l - l % K + K; while (l + K - 1 <= r) { res = max(res, maxInverse[l / K]); auto it = s[l / K].lower_bound(maxVal); if (it != s[l / K].begin()) { --it; res = max(res, *it + maxVal); } maxVal = max(maxVal, *s[l / K].rbegin()); l += K; } if (l <= r) { set<int> tmp; for (int i = l; i <= r; ++i) { tmp.insert(a[i]); } auto it = tmp.lower_bound(maxVal); if (it != tmp.begin()) { --it; res = max(res, *it + maxVal); } res = max(res, calcMaxInv(a, l, r)); } return res; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<int> a(n); for (auto& i : a) { cin >> i; } for (int i = 0; i < n; ++i) { s[i / K].insert(a[i]); } for (int i = 0; (i + 1) * K - 1 < n; ++i) { maxInverse[i] = calcMaxInv(a, i * K, (i + 1) * K - 1); } // while (m--) { // int l, r, k; // cin >> l >> r >> k; // --l, --r; // cout << (calcMaxInv2(a, l, r) <= k) << '\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...