// It's the evening of another day. And the end of mine...
#pragma GCC optimize("O3")
#pragma GCC optimize("fast-math")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
// #include<ext/pb_ds/assoc_container.hpp> \
#include<ext/pb_ds/tree_policy.hpp> \
using namespace __gnu_pbds; \
template<class T> \
using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statisticslmode_update>;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
string sp=" ";
#define F ୨୧
#define fr first
#define er erase
#define sc second
#define in insert
#define ll long long
#define pb push_back
#define mkp make_pair
#define qll queue<ll>
#define dqll deque<ll>
#define mll map<ll,ll>
#define vll vector<ll>
#define pll pair<ll,ll>
#define ull unsigned ll
#define mne min_element
#define mxe max_element
#define rs(x)resize(x)
#define vpll vector<pll>
#define vvll vector<vll>
#define pq priority_queue
#define len(x)(ll)x.size()
#define lcm(x,y)x/__gcd(x,y)*y
#define all(x)x.begin(),x.end()
#define umll unordered_map<ll,ll>
#define lg2(x)(63ll-__builtin_clzll(x))
#define precision(x)fixed<<setprecision(x)
#define popcnt(x)(ll)__builtin_popcountll(x)
template<typename t1,typename t2>istream&operator>>(istream&is,pair<t1,t2>&x){return is>>x.fr>>x.sc;}
template<typename t1,typename t2>ostream&operator<<(ostream&os,pair<t1,t2>&x){return os<<x.fr<<' '<<x.sc;}
template<typename t1>istream&operator>>(istream&is,vector<t1>&vc){for(t1&j:vc)is>>j;return is;}
template<typename t1>ostream&operator<<(ostream&os,vector<t1>&vc){for(t1&j:vc)os<<j<<sp;return os;}
// #define ll int_fast32_t
// #define ll int_fast64_t
// #pragma GCC optimize("O2")
// #pragma GCC target("avx,avx2,fma")
// #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native")
const ll INF=1e9;
const ll INFL=1e18;
const ll MOD=1e9+7;
// const ll MOD=998244353;
const ll maxn=1e6+5;
ll n,m,k=0;
inline void prc(){}
ll tree[4*maxn], a[maxn];
void upd(ll x, ll val, ll l=1, ll r=n, ll v=1){
if(l == r){
tree[v] = val;
return;
}
ll md = (l+r)>>1;
if(x <= md) upd(x, val, l, md, v<<1);
else upd(x, val, md+1, r, v<<1|1);
tree[v] = max(tree[v<<1], tree[v<<1|1]);
}
ll get(ll _l, ll _r, ll l=1, ll r=n, ll v=1){
bool in = _l <= l and r <= _r;
bool ot = _l <= r and l <= _r;
if(in) return tree[v];
if(ot){
ll md = (l+r)>>1;
return max(get(_l, _r, l, md, v<<1),
get(_l, _r, md+1, r, v<<1|1));
}
return 0;
}
void _(ll&tt){
cin>>n>>m;
vll cv(m);
for(ll i=1;i<=n;i++) cin>>a[i];
vvll s(m, vll(4));
for(ll i=0;i<m;i++) cin>>s[i][0]>>s[i][1]>>s[i][2], s[i][3] = i;
sort(all(s), [&](auto a, auto b){ if(a[1] != b[1]) return a[1] < b[1]; return a < b; });
stack<ll>st;
for(ll i=0;i<m;i++){
ll l = s[i][0], r = s[i][1];
for(ll j=k+1;j<=r;j++){
while(!st.empty() and a[st.top()] <= a[j]) st.pop();
if(!st.empty()) upd(st.top(), a[st.top()] + a[j]);
st.push(j);
}
k = max(k, r);
cv[s[i][3]] = (get(l, r) <= s[i][2]);
}
for(ll i=0;i<m;i++) cout<<cv[i]<<'\n';
}
signed main(){
clock_t testcaseruntime=clock();
cin.tie(0)->sync_with_stdio(0);
prc();
ll t=1;
// cin>>t;
for(ll tt=1;tt<=t;tt++){
// cout<<"Case "<<tt<<": ";
_(tt);
}
cerr<<"\n\033[1;31mTime: \033[1;30m"<<(double)(clock()-testcaseruntime)/CLOCKS_PER_SEC<<"\033[1;32m seconds"<<'\n';
}
# | 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... |