Submission #1177887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177887		escobrand	Trampoline (info1cup20_trampoline)	C++20	42 / 100	2099 ms	138104 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,x,X,y,Y,m;
const int maxn = 2e5 + 10,maxv = 20;
map<int,vector<int>>mp;
map<pair<int,int>,int> p[maxv];
vector<pair<int,int>> vec;
int u[maxn],v[maxn];
map<int,int> com;
struct bruh
{
  int aa,bb,cc,dd;
  void inpu()
  {
    cin>>aa>>bb>>cc>>dd;
    com[aa];
    com[bb];
    com[cc];
    com[dd];
  }
}qr[maxn];

void solve(int id)
{
  cin>>y>>x>>Y>>X;
  y = com[qr[id].aa];
  x = com[qr[id].bb];
  Y = com[qr[id].cc];
  X = com[qr[id].dd];
  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)
    {
      if(p[i][make_pair(y,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[i]>>v[i];
      com[u[i]];
      com[v[i]];
    }
    
    cin>>m;
    for(i = 1;i<=m;i++)
    {
      qr[i].inpu();
    }
    
    for(auto &k : com)
    {
      k.se = ++t;
    }
    
    for(i = 1;i<=n;i++)
    {
      u[i] = com[u[i]];
      v[i] = com[v[i]];
      mp[u[i]].eb(v[i]);
      vec.eb(make_pair(u[i],v[i]));
    }
    for(auto & [k,a] : mp)
    {
      sort(all(a));
    }
    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])];
      }
    }
    
    for(i = 1;i<=m;i++)solve(i);
    
    return 0;
}

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