Submission #1346881

#TimeUsernameProblemLanguageResultExecution timeMemory
1346881mofumofuTrampoline (info1cup20_trampoline)C++20
0 / 100
380 ms29068 KiB
#include <bits/stdc++.h>
using namespace std;

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "[";
    for (int i = 0; i < v.size(); ++i) os << v[i] << (i == v.size() - 1 ? "" : ", ");
    return os << "]";
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
//#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ti tuple<ll,ll,ll>
#define ff first 
#define ss second
#define rep(i,a,b) for(ll i=(a); i<(b); i++)
#define all(x) x.begin(),x.end()
#define sz(a) ((int) (a).size())
#define nl '\n'
#define cma <<','<<
ll mod = 1e9 + 7;
ll inf = 1e18;
const int maxn = 1e5+5;
const ll lg = 20;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
//uniform_int_distribution<> dist(1, 2);
// inline ld gen_random(ld l, ld r) {
//     return uniform_real_distribution<ld>(l, r)(rng);
// }

struct HLD {
    int n, cur;
    vector<int> siz, top, dep, parent, in, out, seq;
    vector<vector<int>> adj;
    
    HLD(int n) : n(n), siz(n), top(n), dep(n), parent(n, -1), in(n), out(n), seq(n), adj(n), cur(0) {}
    void add_edge(int u, int v) {
        adj[u].pb(v); adj[v].pb(u);
    }
    void work(int root = 0) {
        top[root] = root; dep[root] = 0;
        parent[root] = -1;
        dfs1(root); dfs2(root);
    }
    void dfs1(int u) {
        if (parent[u] != -1)  adj[u].erase(find(all(adj[u]), parent[u]));
        siz[u] = 1;
        for (auto &v : adj[u]) {
            parent[v] = u;
            dep[v] = dep[u] + 1;
            dfs1(v);
            siz[u] += siz[v];
            if (siz[v] > siz[adj[u][0]]) swap(v, adj[u][0]);
        }
    }
    void dfs2(int u) {
        in[u] = cur++;
        seq[in[u]] = u;
        for (auto v : adj[u]) {
            top[v] = v == adj[u][0] ? top[u] : v;
            dfs2(v);
        }
        out[u] = cur - 1;
    }
    int lca(int u, int v) {
        while (top[u] != top[v]) {
            if (dep[top[u]] > dep[top[v]]) u = parent[top[u]];
			else v = parent[top[v]];
        }
        return dep[u] < dep[v] ? u : v;
    }
    int dist(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    int jump(int u, int k) {
        if (dep[u] < k) return -1;
        int d = dep[u] - k;
        while (dep[top[u]] > d) u = parent[top[u]];
        return seq[in[u] - dep[u] + d];
    }
    //is u ancestor of v
    bool isanc(int u, int v) {
        return in[u] <= in[v] && out[u] >= out[v];
    }
    // child of u that is ancestor of v
    int rootedChild(int u, int v) {
        if (u == v) return u;
        if (!isanc(u, v)) return parent[u];
        auto it = upper_bound(all(adj[u]), v, [&](int x, int y) {
            return in[x] < in[y];
        }) - 1;
        return *it;
    }
    //size of subtree of v when rooted at u
    int rootedSize(int u, int v) {
        if (u == v) return n;
        if (!isanc(v, u)) return siz[v];
        return n - siz[rootedChild(v, u)];
    }
    
    int rootedLca(int a, int b, int c) {
        return lca(a, b) ^ lca(b, c) ^ lca(c, a);
    }
};

int main(){ 
    ios::sync_with_stdio(0);
    cin.tie(0);

    int r, c, n;
    cin >> r >> c >> n;

    map<int, vector<pii>> mp;
    vector<pii> tp;
    rep(i, 0, n) {
        int x, y;
        cin >> x >> y;
        mp[x].emplace_back(y, i);
        tp.emplace_back(x, y);
    }

    for(auto [_, v] : mp) {
        sort(all(v));
    }

    auto find_par = [&](int x, int y) {
        if (x == 1) return -1;

        auto it = upper_bound(all(mp[x - 1]), make_pair(y, n + 1));
        if (it == mp[x - 1].begin()) return -1;
        it--;
        return (*it).ss;
    };

    HLD g(n);
    vector<int> parent(n);
    rep(i, 0, n) {
        int p = find_par(tp[i].ff, tp[i].ss);
        parent[i] = p;
        if (p != -1) {
            g.add_edge(i, p);
        }
    }
    rep(i, 0, n) {
        if (parent[i] == -1) {
            g.work(i);
        }
    }

    int q; cin >> q;
    while (q--) {
        int xs, ys, xe, ye;
        cin >> xs >> ys >> xe >> ye;
        if (ys > ye || xs > xe) {
            cout << "No" << nl;
            continue;
        }

        if (xs == xe) {
            cout << "Yes" << nl;
            continue;
        }

        int j = find_par(xe, ye);
        if (j == -1) {
            cout << "No" << nl;
            continue;
        }

        int k = xe - xs - 1;
        int i = g.jump(j, k);

        if (i == -1) {
            cout << "No" << nl;
            continue;
        }

        cout << (tp[i].ss >= ys ? "Yes" : "No") << nl;
    }



}
/*


*/
#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...