This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int n,q;
int a[1000005];
int tree[1000005];
void upd(int id,int val) {
while(id>0) {
tree[id]=max(tree[id],val);
id-=(id&(-id));
}
}
int get(int id) {
int maxx=-2e9;
while(id<=n) {
maxx=max(maxx,tree[id]);
id+=(id&(-id));
}
return maxx;
}
struct que {
int l,r,k,id;
} qu[1000005];
bool cmp(que a,que b) {
return a.r<b.r;
}
int ans[1000005];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
for(int i=1; i<=n; i++)cin>>a[i];
for(int i=1; i<=q; i++) {
int l,r,k;
cin>>l>>r>>k;
qu[i]= {l,r,k,i};
}
for(int i=1;i<=n;i++)tree[i]=-2e9;
sort(qu+1,qu+q+1,cmp);
int dd=0;
stack<int>st;
for(int i=1; i<=q; i++) {
while(dd+1<=qu[i].r) {
dd++;
while(st.size()&&a[st.top()]<=a[dd])st.pop();
if(st.size()>0){upd(st.top(),a[st.top()]+a[dd]);}
st.push(dd);
}
if(get(qu[i].l)>qu[i].k)ans[qu[i].id]=0;
else ans[qu[i].id]=1;
}
for(int i=1; i<=q; i++)cout<<ans[i]<<'\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |