Submission #681034

#TimeUsernameProblemLanguageResultExecution timeMemory
681034Matteo_VerzHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++17
17 / 100
3068 ms27668 KiB
#include <iostream> #include <vector> #include <stack> #include <algorithm> using namespace std; struct Query { int l, r, w, idx; }; int main() { int n, k; cin >> n >> k; vector <int> v(n); vector <Query> q(k); for (int i = 0; i < n; i++) cin >> v[i]; for (int i = 0; i < k; i++) { cin >> q[i].l >> q[i].r >> q[i].w; q[i].l--; q[i].r--; q[i].idx = i; } sort(q.begin(), q.end(), [](Query a, Query b) { return a.r < b.r; }); vector <int> rightpos(n, -1), ans(k); stack <int> st; int j = 0; for (int i = 0; i < n; i++) { while (st.size() && v[i] >= v[st.top()]) st.pop(); if (st.size()) rightpos[st.top()] = i; st.push(i); while (j < k && q[j].r == i) { auto qi = q[j]; ans[qi.idx] = 0; for (int pos = i; pos >= qi.l; pos--) if (rightpos[pos] != -1) ans[qi.idx] = max(ans[qi.idx], v[pos] + v[rightpos[pos]]); j++; } } sort(q.begin(), q.end(), [](Query a, Query b) { return a.idx < b.idx; }); for (auto qi : q) { // cerr << qi.ans << '\n'; if (ans[qi.idx] > qi.w) cout << 0 << '\n'; else cout << 1 << '\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...