Submission #1234094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234094		Aisha	Trampoline (info1cup20_trampoline)	C++20	100 / 100	945 ms	96184 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 <vector <int>> v(n, vector <int> (3));
    vector <pair <int, int>> sm(n + 1);
    for (int i = 0; i < n; i ++) {
        cin >> v[i][0] >> v[i][1];
        v[i][2] = i + 1;
        sm[i + 1] = {v[i][0], v[i][1]}; 
    }

    // MAKE Graph 

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

  //  map <pair <int, int>,  vector <pair <int, int>>> g;
    vector <vector <int>> g(n + 1);

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

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

            x_2 = x;
            row_2.push_back({y, i});
        } 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(), make_pair(y, n + 1)) - row_1.begin();
            if (id > 0) {
                int a = x_1, b = row_1[id - 1].first, j = row_1[id - 1].second;
                g[j].push_back(i);
            }

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

            x_1 = x;
            row_1.push_back({y, i});
        }
    }

    // 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;
    vector <vector <int>> up(n + 1, vector <int> (k));
    vector <int> vis(n + 1);
    
    auto dfs = [&](auto&& dfs, int i, int p) -> void {
        vis[i] = 1;

        up[i][0] = p;

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

        for (int x : g[i]) {
            dfs(dfs, x, i);
        }
    };

    for (auto w : v) {
        int x = w[0], y = w[1], i = w[2];
        if (vis[i]) continue;
        dfs(dfs, i, 0);
    }

    // CHECK 

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


    // GREEN trampoline

    map <int, vector <pair <int, int>>> mp;
    for (auto w : v) {
        int x = w[0], y = w[1], i = w[2];
    //    cout << x << ' ' << y << endl;
        mp[x].push_back({y, i});
    }


    // 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(), make_pair(y2, n + 1)) - mp[a].begin() - 1;
        int d = a - x1;
        
        if (b == -1) return 0;
        int i = mp[a][b].second;
        b = mp[a][b].first;

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

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

                d -= (1ll << j);
                i = up[i][j];

                a = sm[i].ff, b = sm[i].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: 27 / 27