Submission #1177880

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177880		MinhKien	Trampoline (info1cup20_trampoline)	C++20	100 / 100	220 ms	44080 KiB

trampoline

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

#define ii pair <int, int>
#define fi first
#define se second

const int N = 2e5 + 10;
const int M = 6e5 + 10;

int r, c, n, q, nxt[N][20];
ii a[N];
vector <int> xs;
vector <ii> posy[M];

struct query {
    int x1, y1, x2, y2;

    void input() {
        cin >> x1 >> y1 >> x2 >> y2;
        xs.push_back(x1);
        xs.push_back(x2);
    }
} Q[N];

void input() {
    cin >> r >> c >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].fi >> a[i].se;
        xs.push_back(a[i].fi);
    }
    sort(a + 1, a + n + 1);

    cin >> q;
    for (int i = 1; i <= q; ++i) {
        Q[i].input();
    }

    sort(xs.begin(), xs.end());
    xs.erase(unique(xs.begin(), xs.end()), xs.end());
}

int id(vector <int> &vals, int p) {
    return lower_bound(vals.begin(), vals.end(), p) - vals.begin();
}

int go(int st, int step) {
    for (int i = 0; (1 << i) <= n; ++i) {
        if (step >> i & 1) st = nxt[st][i];
    }
    return st;
}

void solve() {
    int it = (int)xs.size() - 1;
    for (int i = n; i >= 1; --i) {
        while (xs[it] > a[i].fi) --it;
        posy[it].push_back(ii(a[i].se, i));
    }

    for (int i = 0; i < xs.size(); ++i) {
        sort(posy[i].begin(), posy[i].end());
    }

    it = (int)xs.size() - 1;
    for (int i = n; i >= 1; --i) {
        while (xs[it] > a[i].fi) --it;

        if (it == (int)xs.size() - 1 || xs[it] + 1 != xs[it + 1]) {
            nxt[i][0] = 0;
            continue;
        }

        if (posy[it + 1].empty()) nxt[i][0] = 0;
        else {
            vector <ii> :: iterator next_row = lower_bound(posy[it + 1].begin(), posy[it + 1].end(), ii(a[i].se, 0));
            if (next_row == posy[it + 1].end()) nxt[i][0] = 0;
            else nxt[i][0] = (*next_row).se;
        }
    }

    for (int j = 1; (1 << j) <= n; ++j) {
        for (int i = 1; i <= n; ++i) {
            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
        }
    }

    for (int i = 1; i <= q; ++i) {
        if (Q[i].x2 - Q[i].x1 > n || Q[i].x1 > Q[i].x2) {
            cout << "No\n";
            continue;
        }

        if (Q[i].x1 == Q[i].x2) {
            if (Q[i].y1 > Q[i].y2) cout << "No\n";
            else cout << "Yes\n";
            continue;
        }

        int cur = id(xs, Q[i].x1);
        vector <ii> :: iterator pos = lower_bound(posy[cur].begin(), posy[cur].end(), ii(Q[i].y1, 0));
        if (pos == posy[cur].end()) {
            cout << "No\n";
        } else {
            int last = go((*pos).se, Q[i].x2 - Q[i].x1 - 1);
            if (last == 0 || a[last].se > Q[i].y2) cout << "No\n";
            else cout << "Yes\n";
        }
    }
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    input();
    solve();

    return 0;
}

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