Submission #227899

#TimeUsernameProblemLanguageResultExecution timeMemory
227899emil_physmathHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
64 / 100
917 ms262144 KiB
#include <algorithm> #include <iostream> #include <vector> using namespace std; vector<int> a; int w[1000'000], ans[1000'000]; vector<int> t[4000'000]; int tans[4000'000], p[4000'000]; inline int Max(const vector<int>& x) { return x.back(); } void Build(int v, int vl, int vr) { p[v] = vr - vl; if (vl == vr) { ans[v] = 0; t[v].push_back(a[vr]); return; } int m = vl + (vr - vl) / 2; Build(v * 2, vl, m); Build(v * 2 + 1, m + 1, vr); t[v].reserve(vr - vl + 1); merge(t[v * 2].begin(), t[v * 2].end(), t[v * 2 + 1].begin(), t[v * 2 + 1].end(), back_inserter(t[v])); tans[v] = max(tans[v * 2], tans[v * 2 + 1]); auto smaller = lower_bound(t[v * 2 + 1].begin(), t[v * 2 + 1].end(), Max(t[v * 2])); if (smaller != t[v * 2 + 1].begin()) tans[v] = max(tans[v], Max(t[v * 2]) + *--smaller); } struct UPD { int v, maxAtLeft, q; }; vector<UPD> upd; int Query(int v, int vl, int vr, int l, int r, int maxAtLeft, int q) { if (l > vr || vl > r) return 0; if (l <= vl && vr <= r) { ans[q] = max(ans[q], tans[v]); upd.push_back(UPD()); upd.back().v = v; upd.back().maxAtLeft = maxAtLeft; upd.back().q = q; return Max(t[v]); } int vm = vl + (vr - vl) / 2; maxAtLeft = max(Query(v * 2, vl, vm, l, r, maxAtLeft, q), maxAtLeft); maxAtLeft = max(Query(v * 2 + 1, vm + 1, vr, l, r, maxAtLeft, q), maxAtLeft); return maxAtLeft; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; a.resize(n); for (int i = 0; i < n; ++i) cin >> a[i]; Build(1, 0, n - 1); vector<int>().swap(a); for (int i = 0; i < m; ++i) { ans[i] = 0; int l, r; cin >> l >> r >> w[i]; Query(1, 0, n - 1, --l, --r, 0, i); } sort(upd.begin(), upd.end(), [](const UPD& l, const UPD& r) { return l.maxAtLeft > r.maxAtLeft; }); for (UPD x: upd) { int v = x.v, maxAtLeft = x.maxAtLeft, q = x.q; while (p[v] >= 0 && t[v][p[v]] >= maxAtLeft) --p[v]; if (p[v] >= 0) ans[q] = max(ans[q], maxAtLeft + t[v][p[v]]); } for (int i = 0; i < m; ++i) cout << (ans[i] <= w[i]) << '\n'; }
#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...