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;
typedef long long ll;
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll maxx = 1e6+66;
ll tr[maxx];
ll n;
vector <ll> ad[maxx];
vector <ll> a(maxx), b(maxx), c(maxx), k(maxx);
void add(ll id, ll val){
while(id > 0){
tr[id] = max(tr[id], val);
id -= id & -id;
}
}
ll get(ll id){
ll s = 0;
while(id <= n){
s = max(s, tr[id]);
id += id & -id;
}
return s;
}
void S()
{
ll m;
cin >> n >> m;
for(int i = 1; i <= n; i ++)
cin >> a[i];
vector <ll> st;
for(int i = 1; i <= m; i ++){
cin >> b[i] >> c[i] >> k[i];
ad[c[i]].push_back(i);
}
vector <bool> ans(m+1);
for(int i = 1; i <= n; i ++){
while(st.size() > 0 && a[i] >= a[st.back()])
st.pop_back();
ll x = (st.size() == 0 ? 0 : st.back());
add(x, a[x] + a[i]);
for(ll it : ad[i])
ans[it] = (get(b[it]) <= k[it]);
st.push_back(i);
}
for(int i = 1; i <= m; i++)
cout << ans[i] << "\n";
}
int main()
{
IOS;
/*int t;
cin >> t;
while(t --)*/
S();
}
# | 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... |