Submission #751931

#	Time	Username	Problem	Language	Result	Execution time	Memory
751931		tch1cherin	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	975 ms	64156 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
struct Event {
  int modl, modr, type;
 
  Event() {}
 
  Event(int _modl, int _modr, int _type) : modl(_modl), modr(_modr), type(_type) {}
};

struct SegmentTree {
  struct Node {
    int Min, Max;
  };

  Node merge(Node a, Node b) {
    return {min(a.Min, b.Min), max(a.Max, b.Max)};
  }

  int size;
  vector<Node> tree;

  SegmentTree() {}

  SegmentTree(vector<Node> a) {
    int n = (int)a.size();
    size = 2 << __lg(n);
    tree.assign(size * 2, {INT_MAX, INT_MIN});
    for (int i = 0; i < n; i++) {
      tree[size + i] = a[i];
    }
    for (int i = size - 1; i > 0; i--) {
      tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
    }
  }

  Node query(int l, int r, int x, int lx, int rx) {
    if (lx >= r || rx <= l) {
      return {INT_MAX, INT_MIN};
    } else if (lx >= l && rx <= r) {
      return tree[x];
    } else {
      int mid = (lx + rx) / 2;
      Node left = query(l, r, x * 2, lx, mid);
      Node right = query(l, r, x * 2 + 1, mid, rx);
      return merge(left, right);
    }
  }

  Node query(int l, int r) {
    return query(l, r + 1, 1, 0, size);
  } 
};

void solve() {
  int N, K;
  cin >> N >> K;
  int M;
  cin >> M;
  vector<int> A(M), B(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i] >> B[i];
    A[i]--, B[i]--;
  }
  vector<vector<Event>> events(N);
  for (int i = 0; i < M; i++) {
    if (A[i] < B[i]) {
      events[A[i]].emplace_back(N, B[i], 1);
      events[min(A[i] + K - 1, B[i])].emplace_back(N, B[i], -1);
    } else {
      events[max(A[i] - K + 1, B[i])].emplace_back(B[i], -1, 1);
      events[A[i]].emplace_back(B[i], -1, -1);
    }
  }
  vector<int> L(N), R(N);
  multiset<int> sl, sr;
  for (int i = 0; i < N; i++) {
    L[i] = i, R[i] = i;
    for (auto [modl, modr, type] : events[i]) {
      if (type == 1) {
        sl.insert(modl);
        sr.insert(modr);
      }
    }
    if (!sl.empty()) {
      L[i] = min(L[i], *sl.begin());
      R[i] = max(R[i], *sr.rbegin());
    }
    for (auto [modl, modr, type] : events[i]) {
      if (type == -1) {
        sl.erase(sl.find(modl));
        sr.erase(sr.find(modr));
      }
    }
  }
  vector<SegmentTree> tree(20);
  vector<SegmentTree::Node> layer(N);
  for (int i = 0; i < N; i++) {
    layer[i] = {L[i], R[i]};
  }
  tree[0] = SegmentTree(layer);
  for (int i = 0; i + 1 < 20; i++) {
    for (int j = 0; j < N; j++) {
      layer[j] = tree[i].query(layer[j].Min, layer[j].Max);  
    }
    tree[i + 1] = SegmentTree(layer);  
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int S, T;
    cin >> S >> T;
    S--, T--;
    SegmentTree::Node x = {S, S};
    int ans = 0;
    bool good = false;
    for (int i = 20 - 1; i >= 0; i--) {
      SegmentTree::Node y = x;
      x = tree[i].query(x.Min, x.Max);
      if (x.Min <= T && T <= x.Max) {
        x = y;
        good = true;
      } else {
        ans += 1 << i;
      }
    }
    if (!good) {
      cout << -1 << "\n";
    } else {
      cout << 1 + ans << "\n";
    }
  }
}
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}

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