제출 #528613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528613		WLZ	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1774 ms	190800 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

struct node {
  int l, r, mn, mx;
  node *left, *right;
};

node *build(int l, int r, const vector<int> &_mn, const vector<int> &_mx) {
  if (l == r) return new node{l, r, _mn[l], _mx[l], nullptr, nullptr};
  node *left = build(l, (l + r) / 2, _mn, _mx), *right = build((l + r) / 2 + 1, r, _mn, _mx);
  return new node{l, r, min(left->mn, right->mn), max(left->mx, right->mx), left, right};
}

pair<int, int> query(node *cur, int l, int r) {
  if (cur->l > r || cur->r < l) return {INF, -INF};
  if (l <= cur->l && cur->r <= r) return {cur->mn, cur->mx};
  auto left = query(cur->left, l, r), right = query(cur->right, l, r);
  return {min(left.first, right.first), max(left.second, right.second)};
}



int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, max_log;
  cin >> n >> k;
  max_log = ceil(log2(n)) + 1; 
  int m;
  cin >> m;
  vector< vector<int> > mx_diff(n + 1), mn_diff(n + 1);
  while (m--) {
    int a, b;
    cin >> a >> b;
    if (a < b) {
      mx_diff[a].push_back(b);
      if (min(a + k, b + 1) <= n) mx_diff[min(a + k, b + 1)].push_back(-b);
    } else {
      mn_diff[a].push_back(b);
      if (max(a - k, b - 1) >= 1) mn_diff[max(a - k, b - 1)].push_back(-b);
    }
  }
  vector<int> mn(n + 1), mx(n + 1);
  iota(mn.begin(), mn.end(), 0);
  iota(mx.begin(), mx.end(), 0);
  map<int, int> mp;
  for (int i = 1; i <= n; i++) {
    for (auto &x : mx_diff[i]) {
      if (x > 0) mp[x]++;
      else if (--mp[-x] == 0) mp.erase(-x);
    }
    if (!mp.empty()) mx[i] = mp.rbegin()->first;
  }
  mp.clear();
  for (int i = n; i >= 1; i--) {
    for (auto &x : mn_diff[i]) {
      if (x > 0) mp[x]++;
      else if (--mp[-x] == 0) mp.erase(-x);
    }
    if (!mp.empty()) mn[i] = mp.begin()->first;
  }
  vector<node*> up(max_log + 1);
  up[0] = build(1, n, mn, mx);
  for (int i = 1; i <= max_log; i++) {
    for (int j = 1; j <= n; j++) {
      tie(mn[j], mx[j]) = query(up[i - 1], mn[j], mx[j]);
    }
    up[i] = build(1, n, mn, mx);
  }
  int q;
  cin >> q;
  while (q--) {
    int s, t;
    cin >> s >> t;
    int l, r;
    tie(l, r) = query(up[max_log], s, s);
    if (t < l || t > r) {
      cout << -1 << '\n';
      continue;
    }
    l = s, r = s;
    int ans = 0;
    for (int i = max_log; i >= 0; i--) {
      int nl, nr;
      tie(nl, nr) = query(up[i], l, r);
      if (t < nl || t > nr) {
        l = nl, r = nr;
        ans += (1 << i);
      }
    }
    cout << ans + 1 << '\n';
  }
  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13