제출 #1341459

#제출 시각아이디문제언어결과실행 시간메모리
1341459thesentroTrampoline (info1cup20_trampoline)C++20
100 / 100
792 ms84680 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define ll long long
ll mod = 998244353;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll binpow(ll a, ll b)
{
    ll res = 1;
    while (b>0)
    {
        if (b&1)
            res = (res*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return res;
}
ll gcd(ll x, ll y)
{
    if (y==0)
        return x;
    return gcd(y, x%y);
}
        
void solve()
{
    ll r,c,n;
    cin>>r>>c>>n;
    map<ll,set<ll>>mp;
    for (int i=1 ; i<=n ; i++)
    {
        ll x,y;
        cin>>x>>y;
        mp[x].insert(y);
    }
    map<ll,map<ll, set<array<ll, 3>>>>mp1;
    ll q;
    cin>>q;
    vector<ll>res(q+1, 0);
    for (int i=1 ; i<=q ; i++)
    {
        ll x,y,x1,y1;
        cin>>x>>y>>x1>>y1;
        if (y1<y or x>x1) continue;
        if (x==x1) 
        {
            res[i] = 1;
            continue;
        }
        auto it = mp[x].lower_bound(y);
        if (it!=mp[x].end())
        {
            mp1[x][*it].insert({x1, y1, i});
        }
    }
    for (auto &i:mp1)
    {
        for (auto &k:i.second)
        {
                while (!k.second.empty())
                {
                    auto it = (*(k.second.begin()));
                    if (it[0]>i.first+1) break;
                    if (it[1]>=k.first)
                        res[it[2]] = 1;
                    k.second.erase(k.second.begin());
                }
                ll cur = k.first;
                auto it = mp[i.first+1].lower_bound(cur);
                if (it!=mp[i.first+1].end())
                {
                    ll to = *it;
                    // cout<<to<<endl;
                    if (mp1[i.first][k.first].size()>mp1[i.first+1][to].size()) 
                        swap(mp1[i.first][k.first], mp1[i.first+1][to]);
                    for (auto j:mp1[i.first][k.first]) mp1[i.first+1][to].insert(j);
                }
            
        }
    }
    for (int i=1 ; i<=q ; i++)
    {
        if (res[i])
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll tt = 1;
    // cin>>tt;
    while (tt--)
    {
        solve();
    }
    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...