Submission #1318418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1318418		Sir_Ahmed_Imran	Trampoline (info1cup20_trampoline)	C++17	100 / 100	727 ms	38608 KiB

trampoline

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\
 
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

const int N = 2e5 + 1;

int x[N];
int y[N];
int a[N][18];
map<int, vector<pii>> v;

void solve(){
    pii pi;
    int n, m, q, x1, y1, x2, y2;
    cin >> n >> m >> q;
    for(int i = 1; i <= q; i++){
        cin >> x[i] >> y[i];
        v[x[i]].append({y[i], i});
    }
    for(auto & [i, j] : v)
        sort(all(j));
    for(auto & [i, u] : v){
        for(auto & [j, p] : u){
            pi = {j, 0};
            if(!v[i + 1].empty() && v[i + 1].back().ff >= j)
                a[p][0] = (*lower_bound(all(v[i + 1]), pi)).ss;
        }
    }
    for(int j = 0; j < 17; j++)
        for(int i = 1; i <= q; i++)
            a[i][j + 1] = a[a[i][j]][j];
    cin >> q;
    while(q--){
        cin >> x1 >> y1 >> x2 >> y2;
        if(x2 < x1 || y2 < y1){
            cout << "No\n";
            continue;
        }
        if(x1 == x2){
            cout << "Yes\n";
            continue;
        }
        pi = {y1, 0};
        auto it = lower_bound(all(v[x1]), pi);
        if(it == v[x1].end() || (*it).ff > y2){
            cout << "No\n";
            continue;
        }
        n = (*it).ss;
        for(int i = 17; i >= 0; i--)
            if(a[n][i] && y[a[n][i]] <= y2)
                n = a[n][i];
        if(x[n] > x2 - 2) cout << "Yes\n";
        else cout << "No\n";
    }
}

int terminator(){
    L0TA;
    int T = 1;
    //cin >> T;
    while(T--)
        solve();
    return 0;
}

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