Submission #1356037

#TimeUsernameProblemLanguageResultExecution timeMemory
1356037gayMi Teleférico (JOI25_ho_t3)C++20
30 / 100
563 ms73012 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 sparse_table {
    vector<vector<ll>> sp;
    void build(vector<ll>& a) {
        ll n = (int)a.size();
        ll lg = __lg(n);
        sp.resize(lg, vector<ll>(n));
        sp[0] = a;
        for (int i = 1; i < lg; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                sp[i][j] = min(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
            }
        }
    }
    ll get(ll l, ll r) {
        if (r - l <= 0) return INF;
        ll i = __lg(r - l);
        return min(sp[i][l], sp[i][r - (1 << i)]);
    }
};

void solve() {
    ll n, m, p;
    cin >> n >> m >> p;
    map<ll, vector<pair<ll, ll>>> ed;
    vector<ll> cord;
    for (int i = 0; i < m; i++) {
        ll a, b, c; cin >> a >> b >> c; a--, b--;
        cord.push_back(c);
        ed[c].emplace_back(a, b);
    }
    vector<ll> step(n);
    multiset<ll> hv;
    for (int i = 1; i < n; i++) {
        hv.insert(0);
    }
    sort(cord.begin(), cord.end());
    cord.resize(unique(cord.begin(), cord.end()) - cord.begin());
    ll len = (int)cord.size();
    vector<ll> rt(len, INF);
    ll id = 0;
    for (int i = 0; i < len; i++) {
        while (id < len && *hv.begin() == 0) {
            for (auto [a, b] : ed[cord[id]]) {
                hv.erase(hv.find(step[b]));
                step[b]++;
                hv.insert(step[b]);
            }
            id++;
        }
        if (*hv.begin() > 0) {
            rt[i] = cord[id - 1];
        }
        for (auto [a, b] : ed[cord[i]]) {
            hv.erase(hv.find(step[b]));
            step[b]--;
            hv.insert(step[b]);
        }
    }
    vector<ll> val(len);
    for (int i = 0; i < len; i++) {
        val[i] = rt[i] - cord[i];
    }
    sparse_table s;
    s.build(val);

    ll q; cin >> q;
    while (q--) {
        ll l, r, x;
        cin >> l >> r >> x;
        ll rf = upper_bound(cord.begin(), cord.end(), l) - cord.begin();
        ll lf = lower_bound(cord.begin(), cord.end(), l - x) - cord.begin();
        bool ans = false;
        if (l - r + s.get(lf, rf) <= x) ans = true;
        if (rf < len && max(0ll, l - cord[rf]) + max(0ll, rt[rf] - r) <= x) ans = true;
        if (ans) cout << "Yes\n";
        else cout << "No\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...