Submission #1177879

#TimeUsernameProblemLanguageResultExecution timeMemory
1177879escobrandTrampoline (info1cup20_trampoline)C++20
0 / 100
2100 ms125444 KiB
#include <bits/stdc++.h>

using namespace std;
#define all(v) v.begin(),v.end()
#define eb push_back
#define ll long long
#define fi first
#define se second
int t,n,i,c,r,u,v,x,X,y,Y;
const int maxn = 2e5 + 10,maxv = 20;
map<int,vector<int>>mp;
map<pair<int,int>,int> p[maxv];
vector<pair<int,int>> vec;

void solve()
{
  cin>>y>>x>>Y>>X;
  if(X < x || Y < y)
  {
    cout<<"No\n";
    return;
  }
  int tmp = Y - y;
  if(tmp == 0)
  {
    cout<<"Yes\n";
    return;
  }
  auto it = lower_bound(all(mp[y]),x);
  if(it != mp[y].end())x = *it;
  else
  {
    cout<<"No\n";
    return;
  }
  tmp--;
  for(int i = maxv-1;i>=0;i--)
  {
    if((tmp >> i)&1)
    {
      x = p[i][make_pair(y,x)];
      y += (1 << i);
    }
  }
  if(x == 0)
  {
    cout<<"No\n";
    return;
  }
  cout<<(x <= X? "Yes\n" : "No\n");
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>r>>c>>n;
    for(i = 1;i<=n;i++)
    {
      cin>>u>>v;
      mp[u].eb(v);
      vec.eb(make_pair(u,v));
    }
    for(pair<int,int> k : vec)
    {
      auto it = lower_bound(all(mp[k.fi + 1]),k.se);
      if(it != mp[k.fi + 1].end())p[0][k] = *it;
    }
    
    for(i = 1;i<maxv;i++)
    {
      for(pair<int,int> k : vec)
      {
        p[i][k] = p[i-1][make_pair(k.fi + (1 << (i - 1)),p[i-1][k])];
      }
    }
    
    cin>>t;
    while(t--)
    {
      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...