#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define int long long
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
int n, l, q;
cin >> n >> l;
map<int, int> mp;
for(int i = 0, x; i < n; ++ i){
cin >> x;
++mp[x];
}
cin >> q;
vector<pair<int, int> > a(mp.begin(), mp.end());
int mn1 = 0, mn2 = 0;
for(int i = 0; i < a.size(); ++ i){
mn1 += (a.back().first - a[i].first) * a[i].second;
mn2 += (a[i].first - a.front().first) * a[i].second;
}
if(min(mn1, mn2) + n + a.back().first + a.front().first > 500000){
for(int i = 0; i < q; ++ i) cout << "No\n";
return 0;
}
for(int i = 1; i < a.size(); ++ i)
a[i].second += a[i-1].second;
vector dp(4, vector(a.size(), vector(a.size(), 1000000000LL)));
int m = a.size();
dp[0][0][m-1] = 0;
dp[1][0][m-1] = a.back().first - a.front().first;
dp[2][0][m-1] = a.back().first - a.front().first;
dp[3][0][m-1] = 0;
for(int L = 0; L < m; ++ L){
for(int R = m - 1; R >= L; -- R){
if(L == 0 && R == m - 1) continue;
int col = n - (a[R].second - (L == 0 ? 0LL : a[L-1].second));
if(L != 0){
dp[0][L][R] = min(dp[0][L][R], dp[0][L-1][R] + (col+1)*(a[L].first - a[L-1].first));
dp[1][L][R] = min(dp[1][L][R], dp[0][L-1][R] + (col+1)*(a[R].first - a[L-1].first));
dp[2][L][R] = min(dp[2][L][R], dp[2][L-1][R] + (col+1)*(a[L].first - a[L-1].first));
dp[3][L][R] = min(dp[3][L][R], dp[2][L-1][R] + (col+1)*(a[R].first - a[L-1].first));
}
if(R != m-1){
dp[0][L][R] = min(dp[0][L][R], dp[1][L][R+1] + (col+1)*(a[R+1].first - a[L].first));
dp[1][L][R] = min(dp[1][L][R], dp[1][L][R+1] + (col+1)*(a[R+1].first - a[R].first));
dp[2][L][R] = min(dp[2][L][R], dp[3][L][R+1] + (col+1)*(a[R+1].first - a[L].first));
dp[3][L][R] = min(dp[3][L][R], dp[3][L][R+1] + (col+1)*(a[R+1].first - a[R].first));
}
}
}
for(int i = 0, s, f, k, sol, id; i < q; ++ i){
cin >> s >> f >> k;
k -= n;
sol = 1e9;
id = lower_bound(a.begin(), a.end(), make_pair(f, 0LL)) - a.begin();
if(id != a.size()){
sol = min(sol, abs(s-a.front().first) + dp[0][id][id] + (n+1)*abs(a[id].first - f));
sol = min(sol, abs(s-a.back().first) + dp[2][id][id] + (n+1)*abs(a[id].first - f));
}
id --;
if(id != -1){
sol = min(sol, abs(s-a.front().first) + dp[0][id][id] + (n+1)*abs(a[id].first - f));
sol = min(sol, abs(s-a.back().first) + dp[2][id][id] + (n+1)*abs(a[id].first - f));
}
cout << (sol <= k ? "Yes\n" : "No\n");
}
return 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |