제출 #1341175

#제출 시각아이디문제언어결과실행 시간메모리
1341175aykhnTrampoline (info1cup20_trampoline)C++17
100 / 100
456 ms30884 KiB
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F

const int LOG = 20;

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int r, c, n;
  cin >> r >> c >> n;
  int x[n], y[n];
  vector<int> mpx;
  for (int i = 0; i < n; i++) cin >> x[i] >> y[i], mpx.push_back(x[i]), mpx.push_back(x[i] + 1);
  sort(mpx.begin(), mpx.end());
  mpx.resize(unique(mpx.begin(), mpx.end()) - mpx.begin());
  vector<array<int, 2>> v[mpx.size()];
  for (int &i : x) i = lower_bound(mpx.begin(), mpx.end(), i) - mpx.begin();
  for (int i = 0; i < n; i++) v[x[i]].push_back({y[i], i});
  for (int i = 0; i < mpx.size(); i++) sort(v[i].begin(), v[i].end());
  auto getnext = [&](int x, int y) {
    if (x >= mpx.size()) return -1;
    auto it = lower_bound(v[x].begin(), v[x].end(), array<int, 2>{y, -1});
    if (it == v[x].end()) return -1;
    return (*it)[1];
  };
  int par[LOG][n];
  for (int i = 0; i < n; i++) {
    par[0][i] = getnext(x[i] + 1, y[i]);
  }
  for (int i = 1; i < LOG; i++) {
    for (int j = 0; j < n; j++) {
      if (par[i - 1][j] == -1) par[i][j] = -1;
      else par[i][j] = par[i - 1][par[i - 1][j]];
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    if (y1 > y2) {
      cout << "No\n";
      continue;
    }
    if (x1 == x2) {
      cout << "Yes\n";
      continue;
    }
    if (!binary_search(mpx.begin(), mpx.end(), x1) || !binary_search(mpx.begin(), mpx.end(), x2)) {
      cout << "No\n";
      continue;
    }
    x1 = lower_bound(mpx.begin(), mpx.end(), x1) - mpx.begin();
    x2 = lower_bound(mpx.begin(), mpx.end(), x2) - mpx.begin();
    int st = getnext(x1, y1);
    for (int i = LOG - 1; st != -1 && i >= 0; i--) {
      if ((x2 - 1 - x[st]) >> i & 1) {
        st = par[i][st];
      }
    }
    if (st == -1 || y[st] > y2) cout << "No\n";
    else cout << "Yes\n";
  }
}
#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...