Submission #1356025

#TimeUsernameProblemLanguageResultExecution timeMemory
1356025gayMi Teleférico (JOI25_ho_t3)C++20
26 / 100
2094 ms26240 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();
    }
}

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]);
        }
    }
    ll q; cin >> q;
    while (q--) {
        ll l, r, x;
        cin >> l >> r >> x;
        bool ans = false;
        for (int i = 0; i < len; i++) {
            ll cost = max(0ll, l - cord[i]) + max(0ll, rt[i] - r);
            if (cost <= 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...