#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define ins insert
#define F first
#define S second
const int N = 5e5 + 7, mod = 998244353;
int a[N], cnt[N];
void solve(){
int n, len;
cin>>n>>len;
int x = 0;
vector<int>v;
for(int i = 1; i <= n; i++){
cin>>a[i];
cnt[a[i]]++;
v.pb(a[i]);
}
sort(all(v));
v.erase(unique(all(v)));
int m = v.size();
int q;
cin>>q;
while(q--){
int s, t, k;
cin>>s>>t>>k;
if(m >= 1010){
cout<<"NO\n";
continue;
}
int res = 1e18;
int sum = abs(s - v[0]), cur = 0;
int lst = v[0];
for(int i = 0; i < m; i++){
sum += (cur + 1) * (v[i] - lst) + cnt[v[i]];
cur += cnt[v[i]];
int add = (v[m - 1] - v[i]) * (cur + 1), cur1 = cur, lst1 = v.back();
for(int j = m - 1; j > i; j--){
add += (cur1 + 1) * (lst1 - v[j]) + cnt[v[j]];
cur1 += cnt[v[j]];
lst1 = v[j];
}
lst = v[i];
if(i == m - 1){
add += abs(v[i] - t) * (n + 1);
}
else{
add += abs(v[i + 1] - t) * (n + 1);
}
res = min(res, sum + add);
}
if(res <= k){
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
}
signed main(){
ios_base :: sync_with_stdio(false);
cin.tie(0);
//freopen("area.in", "r", stdin);
//freopen("area.out", "w", stdout);
int t = 1;
//cin>>t;
while(t--){
solve();
}
}
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |