Submission #381991

#TimeUsernameProblemLanguageResultExecution timeMemory
381991dorijanlendvajHedgehog Daniyar and Algorithms (IZhO19_sortbooks)C++14
100 / 100
2025 ms83492 KiB
#include <bits/stdc++.h> #define x first #define y second #define pii pair<int,int> using ll=long long; #define pb push_back #define eb emplace_back #define vi vector<int> #define vl vector<ll> #define all(a) begin(a),end(a) using namespace std; const int N=1000010,MOD=1e9+7,M=1<<20; const char en='\n'; const ll LLINF=1ll<<60; int n,q,h[N],ans[N],seg[M*2+10]; void upd(int i,int x) { seg[i+=M]=x; for (i/=2;i;i/=2) seg[i]=max(seg[i*2],seg[i*2+1]); } int ge(int l,int r,int lo=0,int hi=M,int i=1) { if (lo>=l && hi<=r) return seg[i]; if (lo>=r || hi<=l) return -1; int mid=(lo+hi)/2; return max(ge(l,r,lo,mid,i*2),ge(l,r,mid,hi,i*2+1)); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); vector<pair<pii,pii>> v; vector<pii> st; st.eb(MOD,-1); memset(seg,-1,sizeof(seg)); cin>>n>>q; for (int i=0;i<n;++i) { cin>>h[i]; while (st.back().x<=h[i]) st.pop_back(); if (st.back().y!=-1) { v.pb({{st.back().x+h[i],-1},{st.back().y,i}}); } st.eb(h[i],i); } for (int i=0;i<q;++i) { int l,r,k; cin>>l>>r>>k; --l; v.pb({{k,i},{l,r}}); } sort(all(v)); reverse(all(v)); for (auto a: v) { //cout<<a.x.x<<' '<<a.x.y<<' '<<a.y.x<<' '<<a.y.y<<en; if (a.x.y==-1) upd(a.y.y,a.y.x); else ans[a.x.y]=(ge(a.y.x,a.y.y)<a.y.x); } for (int i=0;i<q;++i) cout<<ans[i]<<en; }
#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...