Submission #921353

#	Time	Username	Problem	Language	Result	Execution time	Memory
921353		Ianis	Trampoline (info1cup20_trampoline)	C++17	54 / 100	556 ms	61820 KiB

trampoline

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <map>
#include <set>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define endl '\n'
#endif

#define fi first
#define se second

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

using namespace std;

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

struct Point {
   int x, y;
};

int n;
Point a[NMAX];
map<int, map<int, int>> mp;
int dp[LOGN][NMAX];
int lg2[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 i = 2; i <= n; i++)
      lg2[i] = lg2[i >> 1] + 1;

   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 == 0) return u;
   return jump(dp[lg2[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: 0 / 19
• Subtask 5: 0 / 27