#include <bits/stdc++.h>
/*
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target ("avx2")
*/
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_statistics_node_update>;
*/
#define F first
#define S second
#define pb push_back
#define FIO freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)
#define md(a) ((a%mod+mod)%mod)
#define all(a) a.begin(), a.end()
#define MP make_pair
#define lc (id<<1)
#define rc (lc|1)
#define mid (l+r)/2
#define kill(a) cout << a << "\n", exit(0)
#define SZ(a) (ll)a.size()
typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll const maxn=1e6+10, mod=1e9+7, INF=1e18, LOG=60, sq=65;
ll poww(ll a, ll b, ll mod) {
if (b == 0) return 1;
return 1 * poww(1 * a * a % mod, b / 2, mod) * ((b % 2 == 1) ? a : 1) % mod;
}
struct Node{
int ans;
vector<int> vec;
Node(int ans_, vector<int> vec_)
{
ans=ans_;
vec=vec_;
}
Node () {};
} seg[maxn<<2];
int n, q, A[maxn];
Node Merge(Node L, Node R)
{
if(!SZ(L.vec)) return R;
if(!SZ(R.vec)) return L;
vector<int> vec;
for(int j:L.vec) vec.pb(j);
for(int j:R.vec) vec.pb(j);
sort(all(vec));
int ans=max(L.ans, R.ans);
int t=lower_bound(all(R.vec), L.vec.back())-vec.begin();
if(t!=0) ans=max(ans, L.vec.back()+(R.vec[t-1]));
return Node(ans, vec);
return L;
}
void Build(int l=1, int r=n+1, int id=1)
{
if(l==r-1)
{
seg[id]=Node(0, vector<int>{A[l]});
return;
}
Build(l, mid, lc);
Build(mid, r, rc);
seg[id]=Merge(seg[lc], seg[rc]);
}
Node Get(int s, int e, int l=1, int r=n+1, int id=1)
{
if(l>=e || r<=s) return Node(0, vector<int>{});
if(s<=l && r<=e) return seg[id];
return Merge(Get(s, e, l, mid, lc), Get(s, e, mid, r, rc));
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>A[i];
Build();
while(q--)
{
int l, r, k;
cin>>l>>r>>k;
Node nd=Get(l, r+1);
if(nd.ans<=k) cout<<1<<"\n";
else cout<<"0\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... |