Submission #1165856

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165856		hazzle	Trampoline (info1cup20_trampoline)	C++17	100 / 100	456 ms	38684 KiB

trampoline

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using tui = tuple <int, int, int>;

template <typename T>
using prq = priority_queue <T>;

template <typename T>
using pgq = priority_queue <T, vector <T>, greater <T>>;

template <typename T> bool umin(T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> bool umax(T &a, T b) { return a < b ? a = b, 1 : 0; }

const int L = 18;

inline int solve() {
    int r, c, n;
    cin >> r >> c >> n;
    vector<pii> a(n);
    map<int, vector<pii>> mp;
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        mp[x].push_back({y, i});
        a[i] = {x, y};
    }
    for (auto &[x, v] : mp) {
        sort(v.begin(), v.end());
    }
    auto nxt = [&](int x, int y) {
        if (!mp.count(x)) {
            return -1;
        }
        auto &v = mp[x];
        auto it = lower_bound(v.begin(), v.end(), make_pair(y, 0));
        if (it == v.end()) {
            return -1;
        }
        return it->second;
    };
    vector<vector<int>> up(L, vector<int> (n, -1));
    for (int i = 0; i < n; ++i) {
        auto [x, y] = a[i];
        if (~nxt(x + 1, y)) {
            up[0][i] = nxt(x + 1, y);
        }
    }
    for (int i = 1; i < L; ++i) {
        for (int j = 0; j < n; ++j) {
            if (up[i - 1][j] != -1) {
                up[i][j] = up[i - 1][up[i - 1][j]];
            } else {
                up[i][j] = -1;
            }
        }
    }
    int q; cin >> q;
    while (q--) {
        int sx, sy, tx, ty;
        cin >> sx >> sy >> tx >> ty;
        if (sx > tx || sy > ty) {
            cout << "No\n";
            continue;
        } 
        if (sx == tx) {
            cout << "Yes\n";
            continue;
        }
        int need = tx - sx - 1;
        int u = nxt(sx, sy);
        for (int i = 0; i < L && u != -1; ++i) {
            if (need >> i & 1) {
                u = up[i][u];
                need ^= (1 << i);
            }
        }
        cout << (!need && ~u && a[u].second <= ty ? "Yes\n" : "No\n");
    }
    return 0;
}

inline void precalc() {}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tst = 1;
    // cin >> tst;
    precalc();
    while (tst--) solve();
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27