Submission #1346284

#TimeUsernameProblemLanguageResultExecution timeMemory
1346284rahidilbayramliTrampoline (info1cup20_trampoline)C++20
11 / 100
1243 ms62660 KiB
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pb push_back
#define sz(v) (ll)(v.size())
#define f first
#define s second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
const ll sz = 2e5+5;
vector<pll> vv[sz];
vl g[sz];
ll p[20][sz], lev[sz], vis[sz];
void dfs(ll node)
{
    vis[node] = 1;
    for(auto u : g[node])
    {
        if(vis[u])
            continue;
        lev[u] = lev[node] + 1;
        p[0][u] = node;
        dfs(u);
    }
}
ll jump(ll x, ll k)
{
    for(ll i = 0; i < 19; i++)
    {
        if((k >> i) & 1)
            x = p[i][x];
    }
    return x;
}
void solve()
{
    ll n, m, k, i, j;
    cin >> n >> m >> k;
    vector<pll>vect;
    vl v;
    vect.pb({-1, -1});
    set<ll>st;
    for(i = 1; i <= k; i++)
    {
        ll x, y;
        cin >> x >> y;
        vect.pb({x, y});
        v.pb(x);
        v.pb(x+1);
        st.insert(x);
    }
    sort(all(v));
    v.resize(unique(all(v))-v.begin());
    for(i = 1; i < sz(vect); i++)
    {
        ll x = vect[i].f, y = vect[i].s;
        x = lower_bound(all(v), x) - v.begin() + 1;
        vv[x].pb({y, i});
    }
    for(i = 1; i <= k + 1; i++)
    {
        if(sz(vv[i]))
            sort(all(vv[i]));
    }
    for(i = 1; i < sz(vect); i++)
    {
        ll x = vect[i].f, y = vect[i].s;
        ll f = x + 1;
        f = lower_bound(all(v), f) - v.begin() + 1;
        if(sz(vv[f]))
        {
            if(vv[f].back().f >= y){
                pll pr = {y, -1};
                ll lb = lower_bound(all(vv[f]), pr) - vv[f].begin();
                g[vv[f][lb].s].pb(i);
            }
        }
    }
    for(i = k+1; i >= 1; i--)
    {
        if(!vis[i])
            dfs(i);
    }
    for(i = 1; i < 19; i++)
    {
        for(j = 1; j <= k+1; j++)
            p[i][j] = p[i-1][p[i-1][j]];
    }
    ll q;
    cin >> q;
    while(q--)
    {
        ll x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(y1 > y2 || x1 > x2)
        {
            cout << "No\n";
            continue;
        }
        if(x1 == x2)
        {
            cout << "Yes\n";
            continue;
        }
        if(st.find(x1) == st.end())
        {
            cout << "No\n";
            continue;
        }
        x1 = lower_bound(all(v), x1) - v.begin() + 1;
        if(vv[x1].back().f >= y1)
        {
            pll pr = {y1, 0};
            ll lb = lower_bound(all(vv[x1]), pr) - vv[x1].begin();
            ll stt = vv[x1][lb].s;
            ll l = 0, r = k+5, bst=0;
            while(l <= r)
            {
                ll mid = (l + r) / 2;
                ll o = stt;
                ll h = jump(o, mid);
                if(!h)
                    r = mid - 1;
                else    if(vect[h].f < x2)
                {
                    bst = mid;
                    l = mid + 1;
                }
                else
                    r = mid - 1;
            }
            ll h = jump(stt, bst);
            if(vect[h].f == x2 - 1 && vect[h].s <= y2)
                cout << "Yes\n";
            else
                cout << "No\n";
        }
        else
            cout << "No\n";
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll tests = 1;
    //cin >> tests;
    while(tests--)
    {
        solve();
    }
}
#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...