Submission #1177861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177861		escobrand	Trampoline (info1cup20_trampoline)	C++20	0 / 100	2102 ms	213844 KiB

trampoline

#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;
  }
  for(int i = 0;i<maxv;i++)
  {
    if((tmp >> i)&1)
    {
      if(x == 0)
      {
        cout<<"No\n";
        return;
      }
      x = p[i][make_pair(y,x)];
      y += (1 << i);
    }
  }
  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({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;
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27