Submission #1260734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260734		SnowRaven52	Trampoline (info1cup20_trampoline)	C++20	100 / 100	446 ms	66656 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;

struct state {
    int row_idx;
    int col_idx;
    state(int r=-1,int c=-1):row_idx(r),col_idx(c) {}
};

int main() {
    // freopen("main.in", "r", stdin);
	// freopen(".out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int r, c, n; cin >> r >> c >> n;
    unordered_map<int, vector<int>> mp;

    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mp[a].push_back(b);
    }

    vector<int> rows;
    for (auto &p : mp) {
        auto &v = p.second;
        sort(v.begin(), v.end());
        v.erase(unique(v.begin(), v.end()), v.end());
        rows.push_back(p.first);
    }
    sort(rows.begin(), rows.end());

    int k = rows.size();
    unordered_map<int, int> rank_row;
    rank_row.reserve(k * 2);
    for (int i = 0; i < k; i++) rank_row[rows[i]] = i;

    vector<vector<int>> col(k);
    for (int i = 0; i < k; i++) col[i] = move(mp[rows[i]]);

    const int logn = 20;
    vector<vector<state>> nxt(logn, vector<state>());
    vector<int> off(k + 1, 0);
    for (int i = 0; i < k; i++) off[i + 1] = off[i] + (int)col[i].size();
    int s = off[k];

    for (int b = 0; b < logn; b++) nxt[b].assign(s, state(-1, -1));

    auto idx_of = [&](int i, int j) { return off[i] + j; };

    for (int i = 0; i < k; i++) {
        bool consec = (i + 1 < k) && (rows[i + 1] == rows[i] + 1);
        for (int j = 0; j < (int)col[i].size(); j++) {
            if (!consec) continue;
            int v = col[i][j];
            auto &ncol = col[i + 1];
            auto it = lower_bound(ncol.begin(), ncol.end(), v);
            if (it == ncol.end()) continue;
            int nj = it - ncol.begin();
            nxt[0][idx_of(i, j)] = state(i + 1, nj);
        }
    }

    for (int b = 1; b < logn; b++) {
        for (int u = 0; u < s; u++) {
            state mid = nxt[b - 1][u];
            if (mid.row_idx == -1) {
                nxt[b][u] = state(-1, -1);
                continue;
            }
            int mid_flat = idx_of(mid.row_idx, mid.col_idx);
            nxt[b][u] = nxt[b - 1][mid_flat];
        }
    }

    int t;
    cin >> t;
    while (t--) {
        int xs, ys, xt, yt;
        cin >> xs >> ys >> xt >> yt;

        if (xs > xt || ys > yt) {
            cout << "No" << endl;
            continue;
        }
        if (xs == xt) {
            cout << "Yes" << endl;
            continue;
        }

        int d = xt - xs;
        if (!rank_row.count(xs) || !rank_row.count(xt - 1)) {
            cout << "No" << endl;
            continue;
        }

        int rs = rank_row[xs], re = rank_row[xt - 1];
        if (re - rs != (xt - 1) - xs) {
            cout << "No" << endl;
            continue;
        }

        auto &c0 = col[rs];
        auto it0 = lower_bound(c0.begin(), c0.end(), ys);
        if (it0 == c0.end() || *it0 > yt) {
            cout << "No" << endl;
            continue;
        }

        int j = it0 - c0.begin();
        int flat = idx_of(rs, j);

        int need = d - 1;
        for (int b = 0; b < logn; b++) {
            if (need & (1 << b)) {
                state ns = nxt[b][flat];
                if (ns.row_idx == -1) {
                    flat = -1;
                    break;
                }
                flat = idx_of(ns.row_idx, ns.col_idx);
            }
        }

        if (flat == -1) {
            cout << "No" << endl;
            continue;
        }

        int rcur = upper_bound(off.begin(), off.end(), flat) - off.begin() - 1;
        int kcur = flat - off[rcur];
        int val = col[rcur][kcur];
        cout << (val <= yt ? "Yes" : "No") << endl;
    }
}

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