제출 #1351413

#제출 시각아이디문제언어결과실행 시간메모리
1351413gayMarathon Race 2 (JOI24_ho_t3)C++20
7 / 100
0 ms348 KiB
#include <bits/stdc++.h>
#include <experimental/random>
#include <random>

//#include <ext/pb_ds/assoc_container.hpp>
//using namespace __gnu_pbds;

using namespace std;

using ld = long double;
using ll = long long;

const ll INF = 1e18, MOD = 1e9 + 7;

void solve();

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) {
        solve();
    }
}

struct sol {
    vector<ll> elem;
    ll calc(ll s, ll t) {
        ll lf = elem.front(), rf = elem.back();
        if (t >= rf) {
            ll ans = (int)elem.size() + abs(s - lf) + abs(t - lf);
            for (auto x : elem) {
                ans += abs(t - x);
            }
            return ans;
        }
        ll ans1 = (int)elem.size() + abs(rf - s) + abs(rf - t);
        ll cnt = 0;
        for (auto x : elem) {
            if (x <= t) {
                ans1 += t - x;
                cnt++;
            } else {
                ans1 += x - t;
            }
        }
        ans1 += cnt * 2 * abs(rf - t);

        ll ans2 = (int)elem.size() + abs(rf - s) + abs(rf - lf) + abs(t - lf);
        cnt = 0;
        for (auto x : elem) {
            if (x <= t) {
                ans2 += t - x;
            } else {
                cnt++;
                ans2 += x - t;
            }
        }
        ans2 += cnt * 2 * abs(t - lf);
        return min(ans1, ans2);
    }
};

sol s1, s2;
ll mn = INF, mx = -INF;
ll l;

ll get(ll s, ll t) {
    if (mn <= s && s <= mx && mn <= t && t <= mx) {
        return min(s - mn + s1.calc(mn, t), mx - s + s2.calc(l - mx, l - t));
    }
    if (s <= t) {
        return s1.calc(s, t);
    } else {
        return s2.calc(l - s, l - t);
    }
}

void solve() {
    ll n;
    cin >> n >> l;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        s1.elem.push_back(x);
        mn = min(mn, x);
        mx = max(mx, x);
        s2.elem.push_back(l - x);
    }
    sort(s1.elem.begin(), s1.elem.end());
    sort(s2.elem.begin(), s2.elem.end());
    ll q; cin >> q;
    while (q--) {
        ll s, g, t;
        cin >> s >> g >> t;
        if (get(s, g) <= t) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...