Submission #993227

#TimeUsernameProblemLanguageResultExecution timeMemory
993227serkanrashidHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
0 / 100
938 ms105300 KiB
#include <bits/stdc++.h> #define endl "\n" using namespace std; struct qqq { int l,k,num; qqq(){} qqq(int li, int ki, int ni) { l = li; k = ki; num = ni; } }; const int maxn = 1e6+5; int n,m,w[maxn]; pair<int,int> inv[maxn]; vector<qqq> q[maxn]; int ans[maxn],tree[4*maxn]; int ql,qr,val; void make_bigidx() { w[0] = 1e9+1; stack<int>s1; s1.push(0); for(int i = 1; i <= n; i++) { while(!s1.empty()&&w[s1.top()]<w[i]) s1.pop(); inv[i].first = w[i] + w[s1.top()]; inv[i].second = s1.top(); s1.push(i); } } void read() { cin >> n >> m; for(int i = 1; i <= n; i++) cin >> w[i]; make_bigidx(); int l,r,k; for(int i = 1; i <= m; i++) { cin >> l >> r >> k; q[r].push_back({l,k,i}); } } void update(int v, int l, int r) { if(r<ql||qr<l||l>r) return; if(ql<=l&&r<=qr) { tree[v] = max(tree[v],val); return; } int mid = (l+r)/2; update(v*2+0,l,mid+0); update(v*2+1,mid+1,r); tree[v] = max(tree[v*2+0],tree[v*2+1]); } int query(int v, int l, int r) { if(r<ql||qr<l||l>r) return 0; if(ql<=l&&r<=qr)return tree[v]; int mid = (l+r)/2; return max(query(v*2+0,l,mid+0),query(v*2+1,mid+1,r)); } void solve() { for(int i = 1; i <= n; i++) { if(inv[i].second != 0) { ql = qr = inv[i].second; val = inv[i].first; update(1,1,n); } for(qqq nb : q[i]) { ql = nb.l; qr = i; ans[nb.num] = (nb.k >= query(1,1,n)); } } for(int i = 1; i <= m; i++) cout << ans[i] << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); read(); solve(); 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...