Submission #1234000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234000		Aisha	Trampoline (info1cup20_trampoline)	C++20	0 / 100	821 ms	134976 KiB

trampoline

#include "bits/stdc++.h"

using namespace std;

#define int long long
#define ff first
#define ss second

signed main() {
    // INPUT 
    int r, c, n;
    cin >> r >> c >> n;

    vector <pair <int, int>> v(n);
    for (int i = 0; i < n; i ++) cin >> v[i].ff >> v[i].ss;

    // MAKE Graph

    sort(v.begin(), v.end());

    map <pair <int, int>,  vector <pair <int, int>>> g;

    vector <int> row_1, row_2; 
    int x_1 = 0, x_2 = 0;

    for (auto [x, y] : v) {
        if (x_1 == 0) x_1 = x, row_1.push_back(y);
        else if (x_1 == x) row_1.push_back(y);
        else if (x_1 + 1 == x) {
            int id = upper_bound(row_1.begin(), row_1.end(), y) - row_1.begin();
            if (id > 0) {
                int a = x_1, b = row_1[id - 1];
                g[{a, b}].push_back({x, y});
            }

            x_2 = x;
            row_2.push_back(y);
        } else if (x_2 + 1 == x) {
            row_1.swap(row_2);
            x_1 = x_2;
            row_2.clear();

            int id = upper_bound(row_1.begin(), row_1.end(), y) - row_1.begin();
            if (id > 0) {
                int a = x_1, b = row_1[id - 1];
                g[{a, b}].push_back({x, y});
            }

            x_2 = x;
            row_2.push_back(y);
        } else {
            row_1.clear();
            row_2.clear();

            x_1 = x;
            row_1.push_back(y);
        }
    }

    // CHECK

    /*
    for (auto [p, v] : g) {
        cout << p.ff << ' ' << p.ss << endl;
        for (auto [x, y] : v) {
            cout << x << ' ' << y << endl;
        }

        cout << endl;
    }
    */


    // BINARY JUMPING / DFS

    map <pair <int, int>, vector <pair <int, int>>> up;
    map <pair <int, int>, int> vis;

    int k = 21;
    up[{0, 0}].assign(k, {0, 0});
    
    auto dfs = [&](auto&& dfs, int x, int y, int px, int py) -> void {
        vis[{x, y}] = 1;

        up[{x, y}].assign(k, {0, 0});
        up[{x, y}][0] = {px, py};

        for (int i = 1; i < k; i ++) {
            up[{x, y}][i] = up[up[{x, y}][i - 1]][i - 1];
        }

        for (auto [a, b] : g[{x, y}]) {
            dfs(dfs, a, b, x, y);
        }
    };

    for (auto [x, y] : v) {
        if (vis[{x, y}]) continue;
        dfs(dfs, x, y, 0, 0);
    }


    // CHECK 

    /*
    for (auto [x, y] : v) {
        cout << up[{x, y}][0].ff << ' ' << up[{x, y}][0].ss << endl;
    }
    */


    // FIND 

    auto find = [&](int x1, int y1, int x2, int y2) -> int {
        if (x2 < x1) return 0;
        // x1 y1 dan x2 ga cha yo'l

        // p[x1].x = x1 + 1 
        
        // x1 ning x2 - x1 chi otasi  = x2

        int d = x2 - x1;
        int a = x2, b = y2;
        for (int i = k - 1; i >= 0; i --) {
            if (d >= (1ll << i)) {
                d -= (1ll << i);
                pair <int, int> p = up[{a, b}][i];
                a = p.ff, b = p.ss;
            }
        }

        if (a == x1 && b >= y1) return 1;
        return 0;
    };


    // GET Ans

    auto get_ans = [&](int x1, int y1, int x2, int y2) -> int {
        return find(x1, y1, x2, y2);
    };

    // QUERIES

    int t;
    cin >> t;

    while (t --) {
        int start_x, start_y, stop_x, stop_y;
        int ans = get_ans(start_x, start_y, stop_x, stop_y);
        cout << ans;
    }

    return 0;
}

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