| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1126935 | fzyzzz_z | Marathon Race 2 (JOI24_ho_t3) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
const int A = 1001;
const ll inf = (1LL << 61);
inline void amin(ll & x, ll y) {
if (y < x) x = y;
}
#define int ll
int f[N];
ll dp[2][A][A];
ll cost[2][A];
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, L;
cin >> N >> L;
vector<int> X(N);
for (auto & x: X) cin >> x;
sort(X.begin(), X.end());
vector<pair<int, int>> a(1, {X[0], 0});
for (auto x: X) {
if (x == a.back().first) a.back().second++;
else a.emplace_back(x, 1);
}
int q;
cin >> q;
int n = a.size();
if (n > 1000) {
while (q--) {
cout << "No\n";
}
exit(0);
}
for (int i = 0; i <= L + 1; ++i) f[i] = 0;
for (auto [x, c]: a) f[x + 1] += c;
for (int i = 0; i <= L; ++i) f[i + 1] += f[i];
for (int t = 0; t < 2; ++t) {
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) dp[0][i][j] = dp[1][i][j] = inf;
dp[t][0][n - 1] = 0; // accounted for all outside of (i, j), at 0L or 1R
for (int len = n - 1; len > 0; --len) {
for (int l = 0, r = len; r < n; l++, r++) {
ll has = 0;
ll pl = a[l].first;
ll pl1 = a[l + 1].first;
ll pr1 = a[r - 1].first;
ll pr = a[r].first;
has += f[pl];
has += f[L + 1] - f[pr + 1];
has++;
amin(dp[0][l + 1][r], dp[0][l][r] + (has + a[l].second) * (pl1 - pl));
amin(dp[1][l][r - 1], dp[0][l][r] + (has) * (2LL * pr - pl - pl1) + 1LL * a[r].second * (pr - pr1));
amin(dp[1][l][r - 1], dp[1][l][r] + (has + a[r].second) * (pr - pr1));
amin(dp[0][l + 1][r], dp[1][l][r] + (has) * (pr + pr1 - 2LL * pl) + 1LL * a[l].second * (pl1 - pl));
}
}
for (int i = 0; i < n; ++i) {
cost[t][i] = dp[t][i][i];
}
}
while (q--) {
int st, en;
ll t;
cin >> st >> en >> t;
t -= f[L + 1];
int lo = 0, hi = n - 1;
while (lo < hi) {
int md = (lo + hi) / 2;
if (a[md].first >= en) hi = md;
else lo = md + 1;
}
ll ans = inf;
for (int i = max(0, lo - 3); i <= min(n - 1, lo + 3); ++i) {
amin(ans, cost[0][i] + abs(st - a[0].first) + (ll) (f[L + 1] + 1) * (abs(en - a[n - 1].first)));
amin(ans, cost[1][i] + abs(st - a[n - 1].first) + (ll) (f[L + 1] + 1) * (abs(en - a[0].first)));
}
if (ans <= t) {
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}