Submission #168503

#TimeUsernameProblemLanguageResultExecution timeMemory
168503IldarKAHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
64 / 100
3094 ms69636 KiB
#include <bits/stdc++.h> using namespace std; bool ans[1000001]; int n, m, a[1000001], t[4000001]; vector < int > inv[1000001]; stack < int > s; vector < pair < pair < int, int >, pair < int, int > > > q; void upd(int v, int tl, int tr, int pos, int val){ if(tl == tr){ t[v] = max(t[v], val); return; } int mid = (tl + tr) / 2; if(mid >= pos){ upd(v + v, tl, mid, pos, val); } else{ upd(v + 1 + v, mid + 1, tr, pos, val); } t[v] = max(t[v + v], t[v + 1 + v]); } int get(int v, int tl, int tr, int l, int r){ if(l > r){ return 0; } if(l == tl && tr == r){ return t[v]; } int mid = (tl + tr) / 2; return max(get(v + v, tl, mid, l, min(r, mid)), get(v + 1 + v, mid + 1, tr, max(l, mid + 1), r)); } int main(){ cin >> n >> m; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = n; i >= 1; i--){ while(!s.empty() && a[s.top()] < a[i]){ inv[i].push_back(s.top()); s.pop(); } s.push(i); } for(int i = 1; i <= m; i++){ int l, r, k; cin >> l >> r >> k; q.push_back({{l, r}, {k, i}}); } sort(q.begin(), q.end()); reverse(q.begin(), q.end()); int l = n; for(int i = 0; i < m; i++){ while(q[i].first.first <= l){ for(auto to : inv[l]){ upd(1, 1, n, to, a[to] + a[l]); } l--; } ans[q[i].second.second] = (get(1, 1, n, 1, q[i].first.second) <= q[i].second.first); } for(int i = 1; i <= m; i++){ cout << ans[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...