제출 #921367

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921367		Ianis	Trampoline (info1cup20_trampoline)	C++17	100 / 100	636 ms	45980 KiB

trampoline

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define endl '\n'

#define fi first
#define se second

#define lsb(x) (x & (-x))

using namespace std;

const int NMAX = 2e5+5;
const int LOGN = 22;

struct Point {
   int x, y;
};

int n;
Point a[NMAX];
map<int, map<int, int>> mp;
int dp[LOGN][NMAX];

void read() {
   int r, c;
   cin >> r >> c >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i].x >> a[i].y;
      mp[a[i].x][a[i].y] = i;
   }
}

void precalc() {
   for (int i = 1; i <= n; i++) {
      auto it = mp[a[i].x + 1].lower_bound(a[i].y);
      if (it != mp[a[i].x + 1].end())
         dp[0][i] = it->se;
   }

   for (int j = 1; 1 << j <= n; j++) {
      for (int i = 1; i <= n; i++)
         dp[j][i] = dp[j - 1][dp[j - 1][i]];
   }
}

int jump(int u, int k) {
   if (k > n) return 0;
   if (k == 0) return u;
   return jump(dp[int(log2(lsb(k)))][u], k ^ lsb(k));
}

Point jump(int x, int y, int k) {
   auto it = mp[x].lower_bound(y);
   if (it == mp[x].end()) return { };
   return a[jump(it->se, k)];
}

bool query(int x1, int y1, int x2, int y2) {
   if (x2 < x1 || y2 < y1) return false;
   if (x1 == x2) return true;
   Point p = jump(x1, y1, x2 - x1 - 1);
   if (!p.x) return false;
   return p.y <= y2;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   read();
   precalc();

   int t = 1;
   cin >> t;

   while (t--) {
      int x1, y1, x2, y2;
      cin >> x1 >> y1 >> x2 >> y2;
      cout << (query(x1, y1, x2, y2) ? "Yes" : "No") << endl;
   }

   return 0;
}

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