Submission #537328

#	Time	Username	Problem	Language	Result	Execution time	Memory
537328		cig32	Trampoline (info1cup20_trampoline)	C++17	100 / 100	921 ms	93656 KiB

trampoline

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 1e6 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
long long bm(long long b, long long p) { 
  if(p==0) return 1;
  long long r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}


void solve(int tc) {
  int r, c, n;
  cin >> r >> c >> n;
  unordered_map<int, set<int> > mp;
  int x[n+1], y[n+1];
  map<pair<int, int>, int> id;
  for(int i=1; i<=n; i++) {
    cin >> x[i] >> y[i];
    id[{x[i], y[i]}] = i;
    mp[x[i]].insert(y[i]);
    mp[x[i] + 1].insert(MOD);
  }

  int st[18][n+1];
  for(int i=1; i<=n; i++) {
    auto it = mp[x[i] + 1].lower_bound(y[i]);
    if((*it) != MOD) {
      int wow = id[{x[i] + 1, (*it)}];
      st[0][i] = wow;
    }
    else {
      st[0][i] = -1;
    }
  }
  for(int i=1; i<18; i++) {
    for(int j=1; j<=n; j++) {
      if(st[i-1][j] == -1) st[i][j] = -1;
      else st[i][j] = st[i-1][st[i-1][j]];
    }
  }
  int t;
  cin >> t;
  while(t--) {
    int xs, ys, xe, ye;
    cin >> xs >> ys >> xe >> ye;
    if(!(xs <= xe && ys <= ye)) {
      cout << "No\n";
      continue;
    }
    if(xs == xe) {
      cout << "Yes\n";
      continue;
    }
    int k = xe - xs - 1;
    mp[xs].insert(MOD);
    auto it = mp[xs].lower_bound(ys);
    int stt;
    if((*it) != MOD) {
      stt = id[{xs, (*it)}];
    }
    else {
      cout << "No\n"; 
      continue;
    }
    bool gg = 0;
    for(int j=17; j>=0; j--) {
      if(k >= (1<<j)) {
        k -= (1<<j);
        stt = st[j][stt];
        if(stt == -1) {
          cout << "No\n";
          gg = 1;
          break;
        } 
      }
    }
    if(!gg) {
      if(y[stt] <= ye) {
        cout << "Yes\n";
      }
      else {
        cout << "No\n";
      }
    }
  }
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}

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