제출 #1234043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1234043		Aisha	Trampoline (info1cup20_trampoline)	C++20	73 / 100	2103 ms	179424 KiB

trampoline

#include "bits/stdc++.h"

using namespace std;

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

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 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;
    }
    */


    // GREEN trampoline

    map <int, vector <int>> mp;
    for (auto [x, y] : v) {
    //    cout << x << ' ' << y << endl;
        mp[x].push_back(y);
    }


    // FIND 

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

        // p[x1].x = x1 + 1 
        
        // x1 ning x2 - x1 chi otasi  = x2
       
     //   cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;

        int a = x2 - 1, b = upper_bound(mp[a].begin(), mp[a].end(), y2) - mp[a].begin() - 1;
        int d = a - x1;

        if (b == -1) return 0;
        b = mp[a][b];

     //   cout << a << ' ' << b << endl;

        for (int i = k - 1; i >= 0; i --) {
            if (d >= (1ll << i)) {
              //  cout << i << endl;

                d -= (1ll << i);
                pair <int, int> p = up[{a, b}][i];

                a = p.ff, b = p.ss;
                // cout << a << ' ' << b << endl;
            }
        }

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


    // GET Ans

    auto get_ans = [&](int x1, int y1, int x2, int y2) -> string {
        return (find(x1, y1, x2, y2) == 1 ? "Yes" : "No");
    };

    // QUERIES

    int t;
    cin >> t;

    while (t --) {
        int start_x, start_y, stop_x, stop_y;
        cin >> start_x >> start_y >> stop_x >> stop_y;

        string ans = get_ans(start_x, start_y, stop_x, stop_y);
     //   cout << "ans = ";
        cout << ans << endl;
      //  cout << endl;
    }

    return 0;
}

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