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;
#define fr first
#define sc second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
typedef long long ll;
const int MAX = 1e6 + 10;
const int INF = 0x3f3f3f3f;
struct Q{
ll l, k, id;
Q(ll a = 0, ll b = 0, ll c = 0){
l = a, k = b, id = c;
}
};
ll n, m, a[MAX], seg[4 * MAX];
bool resp[MAX];
vector<Q> queries[MAX];
void update(ll i, ll x, ll p, ll l, ll r){
if(i < l || i > r) return;
if(l == r){
seg[p] = max(seg[p], x);
return;
}
ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
update(i, x, e, l, m);
update(i, x, d, m + 1, r);
seg[p] = max(seg[e], seg[d]);
}
ll query(ll a, ll b, ll p, ll l, ll r){
if(a > r || b < l) return -INF;
if(a <= l && r <= b) return seg[p];
ll m = (l + r) >> 1, e = 2 * p, d = e + 1;
return max(query(a, b, e, l, m), query(a, b, d, m + 1, r));
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 1; i <= n; i++)
cin >> a[i];
for(int i = 1; i <= m; i++){
ll l, r, k; cin >> l >> r >> k;
queries[r].emplace_back(l, k, i);
}
a[0] = INF;
stack<int> s; s.push(0);
for(int i = 1; i <= n; i++){
while(a[s.top()] <= a[i]) s.pop();
if(s.top() != 0){
int idx = s.top();
update(idx, a[idx] + a[i], 1, 1, n);
}
s.push(i);
for(auto q : queries[i]){
int l = q.l, k = q.k, idx = q.id;
resp[idx] = (query(l, i, 1, 1, n) <= k);
}
}
for(int i = 1; i <= m; i++)
cout << resp[i] << '\n';
exit(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... |