Submission #1059303

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059303		jnjwnwnw	Trampoline (info1cup20_trampoline)	C++17	100 / 100	1008 ms	81492 KiB

trampoline

#include <iostream>
#include <algorithm>    
#include <map>
#include <vector>
#include <set>
using namespace std;

#define ll long long
#define fff(i,a,b) for (int i = a; i < b; i++)
#define fffm(i,a,b) for (int i = a; i > b; i--)

#define MAXN 200005
map<ll, set<pair<ll, ll>>> xs;
ll parent[MAXN][22], Y[MAXN], X[MAXN];
ll R, C, n, T;

// class comp{
//     public:
//     bool operator()(const pair<ll, ll>& a, const pair<ll, ll>& b) const{
//         if (a.first == b.first) return a.second < b.second;
//         return a.first < b.first;
//     }
// };

int main(){
    cin >> R >> C >> n;
    fff(i, 0, n){
        cin >> Y[i] >> X[i];
        xs[Y[i]].insert({X[i], i});
    }

    // for(auto& [a, b]: xs){
    //     sort(b.begin(), b.end());
    // }

    fff(i, 0, n){
        // cout << "A" << endl;
        ll y = Y[i], x = X[i];
        parent[i][0] = i;
        if (xs[y-1].size() == 0) continue;
        // cout << "B" << endl;
        auto ptr = xs[y-1].upper_bound({x, INT32_MAX});
        // if (ptr == xs[y-1].end()) ptr--;
        if (ptr == xs[y-1].begin()) continue;
        ptr--;
        // cout << "C" << endl;
        auto [x2, ind] = *ptr;
        if (x2 > x) continue;
        // cout << "D" << endl;
        // this is fine, so parent here
        parent[i][0] = ind;
        // cout << i << " " << y << " " << x << " " << parent[i][0] << endl;
        // cout << i  << " " << parent[i][0] << endl;
    }

    // now, do LCA stuff
    fff(i, 1, 22){
        fff(j, 0, n){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
    cin >> T;
    fff(i, 0, T){
        ll y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
        if (y2 < y1 || x2 < x1){
            cout << "NO" << endl;
            continue;
        }
        if (y2 == y1){
            cout << "YES" << endl;
            continue;
        }
        if (xs[y2-1].size() == 0){
            cout << "NO" << endl;
            continue;
        }
        auto ptr = xs[y2-1].upper_bound({x2, INT64_MAX});

        if (ptr == xs[y2-1].begin()){
            cout << "NO" << endl;
            continue;
        }
        ptr--;
        // cout << "YAY" << endl;
        ll ind = ptr->second;
        // cout << ind << " " << parent[ind][0] << endl;
        fffm(amt, 21, -1){
            if (Y[parent[ind][amt]] >= y1){
                ind = parent[ind][amt];
                // cout << "AAA " << ind << endl;
            }
        }
        // ind is now at the right level hopefully
        if (Y[ind] != y1 || X[ind] < x1){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;

    }
}

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