Submission #922365

#	Time	Username	Problem	Language	Result	Execution time	Memory
922365		maxFedorchuk	Trampoline (info1cup20_trampoline)	C++17	100 / 100	709 ms	92636 KiB

trampoline

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

const long long MX=2e5+100;

map < long long , set < pair < long long, long long > >> mp;
long long lca[30][MX];
long long col[MX];
long long r,c,n;

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    cin >> r >> c >> n;

    for (long long i = 1; i <= n; i++) {
        long long a, b;
        cin >> a >> b;

        mp[a].insert({b, i});
        col[i] = b;
    }

    for (auto [zr, st]: mp) {
        for (auto [zn, in]: st) {
            auto it = mp[zr + 1].lower_bound({zn, 0});
            if (it != mp[zr + 1].end()) {
                lca[0][in] = (*it).second;
            }
        }
    }

    for (long long sl = 1; sl < 30; sl++) {
        for (long long i = 1; i <= n; i++) {
            lca[sl][i] = lca[sl - 1][lca[sl - 1][i]];
        }
    }

    long long q;
    cin >> q;

    while (q--) {
        long long x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 > x2 || y1 > y2) {
            cout << "No\n";
            continue;
        }

        if (x1 == x2) {
            cout << "Yes\n";
            continue;
        }

        auto st = mp[x1].lower_bound(make_pair(y1, 0));
        if (st == mp[x1].end()) {
            cout << "No\n";
            continue;
        }

        long long rd = x2 - x1 - 1, zr = (*st).second;

        for (long long i = 0; i < 30; i++) {
            if ((rd >> i) & 1) {
                zr = lca[i][zr];
            }
        }

        if (zr != 0 && col[zr] <= y2) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

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