Submission #1314538

#TimeUsernameProblemLanguageResultExecution timeMemory
1314538hynmjTrampoline (info1cup20_trampoline)C++20
0 / 100
107 ms18852 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;
const long long N = 5000 + 5;
int a[N];
int n, m;
const int lg = 19;
int spt[N][lg];
int visited[N];
int pare[N];
vector<int> graph[N];
void dfs(int node, int parent)
{
    visited[node] = 1;
    for (int i : graph[node])
    {
        if (visited[i])
            continue;
        // cout << made
        pare[node] = i;
        dfs(i, node);
    }
}
int c(int i, int j)
{
    return m * (i) + j;
}
pair<int, int> c(int k)
{
    return make_pair(k / m, k % m);
}
void initialize(int n)
{
    n++;
    for (int i = 0; i < n; i++)
        spt[i][0] = pare[i];
    for (int i = 1; i < lg; i++)
        for (int j = 0; j + (1ll << i) <= n; j++)
            spt[j][i] = spt[spt[j][i - 1]][i - 1];
}
int get(int l, int r)
{
    int ch = 31 - __builtin_clz(r - l + 1);
    return min(spt[l][ch], spt[r - (1ll << ch) + 1][ch]);
}

void solve()
{
    int p;
    cin >> n >> m >> p;
    int u, v;
    // n++, m++;
    set<pair<int, int>> green;
    vector<pair<int, int>> indexing;
    for (int i = 0; i < p; i++)
    {
        cin >> u >> v;
        u--, v--;
        int k = c(u, v);
        green.insert({k, i + 1});
        indexing.push_back({u, v});
        // cerr << u << ' ' << v << ' ' << i + 1 << endl;
    }
    for (auto i : green)
    {
        // cout << i.first << ' ' << i.second << endl;
        auto sp = c(i.first);
        sp.first++;
        int k = c(sp.first, sp.second);
        auto x = green.lower_bound({k, 0});
        if (x == green.end() or c(x->first).first > sp.first)
            continue;
        else
        {
            // cout << "made " << sp.second << " " << x->second << endl;
            graph[sp.second].push_back(x->second);
        }
    }
    for (int i = 1; i <= p; i++)
    {
        if (!visited[i])
            dfs(i, 0);
    }
    initialize(p + 2);
    int q;
    cin >> q;
    int x, y, xx, yy;
    for (int i = 0; i < q; i++)
    {

        // cout << q << endl;
        cin >> x >> y >> xx >> yy;
        x--, y--, xx--, yy--;
        if (xx < x or yy < y)
        {
            cout << "No\n";
            continue;
        }
        if (xx == x)
        {
            cout << "Yes\n";
            continue;
            ;
        }
        int k = c(x, y);
        // cout << k << endl;
        auto f = green.lower_bound({k + 1, 0});
        // cout << f->first << ' ' << f->second << endl;
        if (f == green.end())
        {
            cout << "No\n";
            continue;
        }
        int id = f->second;
        auto sup = c((int)f->first);
        // cout << sup.first << endl;
        if (sup.first != x)
        {
            cout << "No\n";
            continue;
        }
        else
        {
            // cout << k << ' ' << id << endl;
            int lk = xx - x - 1;
            // cout << id << ' ' << lk << endl;
            for (int i = lg - 1; i >= 0; i--)
            {
                int mask = 1ll << i;
                if (mask <= lk)
                {
                    lk -= mask;
                    // ;
                    // cerr << id << ' ' << i << endl;
                    id = spt[id][i];
                }
            }
            // cerr << k << ' ' << id << endl;
            // cout << x << ' ' << y << ' ' << xx << ' ' << yy << endl;
            if (id == 0)
            {
                cout << "No\n";
                continue;
            }
            if (indexing[id - 1].first <= xx)
            {
                cout << "Yes\n";
            }
            else
                cout << "No\n";
        }
    }
    // cout << pare[1] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ':' << ' ';
        solve();
        cout << endl;
    }
    return 0;
}
#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...