제출 #1332734

#제출 시각아이디문제언어결과실행 시간메모리
1332734AzeTurk810Trampoline (info1cup20_trampoline)C++20
100 / 100
1034 ms57508 KiB
/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif
constexpr int K = 30;

char solve() {
    int R, C, N;
    if (!(cin >> R >> C >> N))
        return 1;
    vector<pair<int, int>> greens(N);
    map<int, vector<pair<int, int>>> mp;
    set<int> stt;
    for (int i = 0; i < N; i++) {
        cin >> greens[i].first >> greens[i].second;
        mp[greens[i].first].push_back({greens[i].second, i});
        stt.insert(greens[i].first);
    }
    for (int i : stt) {
        sort(mp[i].begin(), mp[i].end());
    }
    vector<vector<int>> st(K, vector<int>(N + 1, N));
    auto nxt = [&] (int i) {
        auto it = lower_bound(mp[greens[i].first + 1].begin(), mp[greens[i].first + 1].end(), make_pair(greens[i].second, -1));
        if (it == mp[greens[i].first + 1].end()) {
            return N;
        }
        return it->second;
    };
    auto cur = [&] (int i, int j) {
        auto it = lower_bound(mp[i].begin(), mp[i].end(), make_pair(j, -1));
        if (it == mp[i].end()) {
            return N;
        }
        return it->second;
    };
    { // build
        for (int i = 0; i < N; i++) {
            st[0][i] = nxt(i);
        }
        for (int i = 1; i < K; i++) {
            for (int j = 0; j < N; j++) {
                st[i][j] = st[i - 1][st[i - 1][j]];
            }
        }
    }
    int Q;
    cin >> Q;
    for (; Q > 0; Q--) {
        int xs, ys, xf, yf;
        cin >> xs >> ys >> xf >> yf;
        if (xs > xf || ys > yf) {
            cout << "No\n";
            continue;
        }
        int id = cur(xs, ys);
        dbg(id);
        if (xs > xf || ys > yf) {
            cout << "No\n";
            continue;
        }
        int tar = xf - xs;
        if (tar == 0) {
            cout << "Yes\n";
            continue;
        }
        tar--;
        for (int i = 0; i < K; i++) {
            if ((1 << i) & tar) {
                id = st[i][id];
            }
        }
        dbg(id);
        if (id == N) {
            cout << "No\n"; 
            continue;
        }
        assert(greens[id].first + 1 == xf);
        if (greens[id].second <= yf) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

// Attack on titan<3

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    int t = 1e9;
    // cin >> t;
    for (int cases = 0; cases < t; cases++) {
        if (solve())
            break;
#ifdef ONPC
        cerr << "__________\n";
#endif
    }
}
// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...