Submission #1072095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072095		duckindog	Event Hopping (BOI22_events)	C++17	100 / 100	106 ms	38592 KiB

events

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, q;
struct Event { 
  int st, ed, idx;
} a[N];
int rvs[N];

int lg[N];

int f[N][19];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> q;
  for (int i = 1; i <= n; ++i) cin >> a[i].st >> a[i].ed, a[i].idx = i;
  sort(a + 1, a + n + 1, [&](const auto& a, const auto& b) { return a.ed < b.ed; });
  for (int i = 1; i <= n; ++i) rvs[a[i].idx] = i;

  for (int i = 2; i < N; ++i) lg[i] = lg[i >> 1] + 1;
  { //init
    vector<int> rrh;
    for (int i = 1; i <= n; ++i) { 
      rrh.push_back(a[i].st);
      rrh.push_back(a[i].ed);
    }
    sort(rrh.begin(), rrh.end());
    rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

    a[0] = {1'000'000, 1'000'000};
    vector<vector<int>> save(rrh.size() + 1);
    for (int i = 1; i <= n; ++i) { 
      a[i].st = upper_bound(rrh.begin(), rrh.end(), a[i].st) - rrh.begin();
      a[i].ed = upper_bound(rrh.begin(), rrh.end(), a[i].ed) - rrh.begin();
      save[a[i].ed].push_back(i);
    }

    vector<array<int, 19>> st(rrh.size() + 1);
    using pii = pair<int, int>;
    priority_queue<pii, vector<pii>, greater<>> q;
    for (int i = 1; i <= rrh.size(); ++i) { 
      for (const auto& idx : save[i]) q.push({a[idx].st, idx});
      while (q.size() && a[q.top().second].ed < i) q.pop();
      st[i][0] = (!q.size() ? 0 : q.top().second);
    }

    for (int j = 1; j <= 18; ++j) { 
      for (int i = 1; i + (1 << j) - 1 <= rrh.size(); ++i) { 
        int lt = st[i][j - 1], rt = st[i + (1 << j - 1)][j - 1];
        st[i][j] = (a[lt].st < a[rt].st ? lt : rt);
      }
    }

    auto get = [&](int l, int r) { 
      int j = lg[r - l + 1];
      int lt = st[l][j], rt = st[r - (1 << j) + 1][j];
      return a[lt].st < a[rt].st ? lt : rt;
    };
    for (int i = 1; i <= n; ++i) f[i][0] = get(a[i].st, a[i].ed);
  }

  auto in = [&](int x, int y) { 
    return a[y].st <= a[x].ed && a[x].ed <= a[y].ed;
  };

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

  while (q--) { 
    int x, y; cin >> x >> y;
    x = rvs[x]; y = rvs[y];

    if (in(x, y)) { cout << 1 - (x == y) << "\n"; continue; }
    if (a[x].st >= a[y].ed) { cout << "impossible\n"; continue; }

    int answer = 1;
    for (int i = 18; i >= 0; --i) { 
      if (!in(x, f[y][i]) && a[f[y][i]].ed >= a[x].ed) { 
        answer += (1 << i);
        y = f[y][i];
      }
    } y = f[y][0];

    if (!in(x, y)) { cout << "impossible\n"; continue; }
    cout << answer + (x != y) << "\n";
  }
}

Compilation message (stderr)

events.cpp: In function 'int32_t main()':
events.cpp:45:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for (int i = 1; i <= rrh.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
events.cpp:52:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |       for (int i = 1; i + (1 << j) - 1 <= rrh.size(); ++i) {
      |                       ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
events.cpp:53:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |         int lt = st[i][j - 1], rt = st[i + (1 << j - 1)][j - 1];
      |                                                  ~~^~~

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