Submission #574164

#	Time	Username	Problem	Language	Result	Execution time	Memory
574164		MilosMilutinovic	Event Hopping (BOI22_events)	C++14	100 / 100	332 ms	42112 KiB

events

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);  
  int n, q;
  cin >> n >> q;
  vector<int> l(n), r(n);
  vector<int> xs;
  for (int i = 0; i < n; i++) {
    cin >> l[i] >> r[i];
    xs.push_back(l[i]);
    xs.push_back(r[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    l[i] = lower_bound(xs.begin(), xs.end(), l[i]) - xs.begin();
    r[i] = lower_bound(xs.begin(), xs.end(), r[i]) - xs.begin();
  }
  /* if (n <= 1000 && q <= 100) {
    while (q--) {
      int x, y;
      cin >> x >> y;
      --x, --y;
      if (x == y) {
        cout << 0 << '\n';
        continue;
      }      
      int ans = 1;
      int idx = x;
      while (idx != y) {
        if (l[y] <= r[idx] && r[idx] <= r[y]) {
          idx = y;
          break;
        }
        int nxt = idx;
        for (int i = 0; i < n; i++) {
          if (l[i] <= r[idx] && r[idx] <= r[i] && r[i] > r[nxt] && r[i] <= r[y]) {
            nxt = i;
          }
        }
        ans += 1;
        if (nxt == idx) {
          break;  
        }
        idx = nxt;
      }
      if (idx != y) {
        cout << "impossible" << '\n';
        continue;
      }
      cout << ans << '\n';
    }
    return 0;
  } */
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int i, int j) {
    if (r[i] != r[j]) {
      return r[i] < r[j];
    } else {
      return l[i] < l[j];
    }
  });
  vector<int> id(n);
  for (int i = 0; i < n; i++) {
    id[order[i]] = i;
  }
  vector<int> xl(n), xr(n);
  for (int i = 0; i < n; i++) {
    xl[i] = l[order[i]];
    xr[i] = r[order[i]];
  }
  swap(l, xl);
  swap(r, xr);        
  const int LOG = 17;               
  vector<vector<pair<int, int>>> who(n, vector<pair<int, int>>(LOG));
  for (int i = 0; i < n; i++) {
    who[i][0] = make_pair(l[i], i);
  }
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i + (1 << j) <= n; i++) {
      who[i][j] = min(who[i][j - 1], who[i + (1 << (j - 1))][j - 1]);
    }
  }
  vector<int> logs(n + 1);
  for (int i = 2; i <= n; i++) {
    logs[i] = logs[i / 2] + 1;
  }
  auto query = [&](int l, int r) {
    int k = logs[r - l + 1];
    return min(who[l][k], who[r - (1 << k) + 1][k]);
  };
  vector<int> prv(n); 
  /* for (int i = 0; i < n; i++) {
    cout << l[i] << " " << r[i] << '\n';
  }
  cout << '\n'; cout << '\n'; */
  for (int i = 0; i < n; i++) {
    int low = 0, high = i; 
    prv[i] = i;
    while (low <= high) {
      int mid = low + high >> 1;
      if (r[mid] >= l[i]) {
        prv[i] = mid;
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    /* cout << "[" << prv[i] + 1 << " " << i + 1 << "]" << '\n'; */
  }
  vector<vector<int>> jump(n, vector<int>(LOG));
  vector<vector<int>> st(n, vector<int>(LOG));
  function<void(int)> buildSparse = [&](int j) {
    for (int i = 0; i < n; i++) {
      st[i][0] = jump[i][j];
    }
    for (int p = 1; p < LOG; p++) {
      for (int i = 0; i + (1 << p) <= n; i++) {
        st[i][p] = min(st[i][p - 1], st[i + (1 << (p - 1))][p - 1]);
      }
    }
  };
  auto get = [&](int l, int r) {
    int k = logs[r - l + 1];
    return min(st[l][k], st[r - (1 << k) + 1][k]);
  };
  for (int i = 0; i < n; i++) {
    jump[i][0] = prv[i];
  }
  for (int j = 1; j < LOG; j++) {
    for (int i = 0; i < n; i++) {
      jump[i][j] = jump[query(jump[i][j - 1], i).second][j - 1]; // min jump[x][j - 1] for x in range [jump[i][j - 1], i]
    }
  }
  while (q--) {
    int x, y;
    cin >> x >> y;
    --x, --y;
    x = id[x];
    y = id[y];
    if (x == y) {
      cout << 0 << '\n';
      continue;
    }
    if (l[y] <= r[x] && r[x] <= r[y]) {
      cout << 1 << '\n';
      continue;
    }
    if (x > y) {
      cout << "impossible" << '\n';
      continue;
    }
    int ans = 0;
    for (int i = LOG - 1; i >= 0; i--) {
      if (jump[y][i] > x) {
        ans += (1 << i);
        y = query(jump[y][i], y).second;
      }
    }
    if (jump[y][0] > x) {
      cout << "impossible" << '\n';
      continue;
    } else {
      ans += 1;
    }
    cout << ans << '\n';
  }
  return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |       int mid = low + high >> 1;
      |                 ~~~~^~~~~~
events.cpp:128:8: warning: variable 'get' set but not used [-Wunused-but-set-variable]
  128 |   auto get = [&](int l, int r) {
      |        ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30