Submission #1169386

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169386		fryingduc	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	1264 ms	120084 KiB

Main

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif


const int maxn = 1e5 + 5;
const int LG = 17;
const int M = 2e5 + 5;
int n, k, m;

pair<int, int> operator + (const pair<int, int> &a, const pair<int, int> &b) {
  return make_pair(min(a.first, b.first), max(a.second, b.second));
}

pair<int, int> inf = make_pair(1e9, 0);

struct segment_tree {
  int n;
  vector<pair<int, int>> tree;
  vector<pair<int, int>> lazy;
  
  segment_tree() {}
  
  segment_tree(int n) : n(n), tree(n * 4 + 6, inf), lazy(n * 4 + 6, inf) {}
  
  void down(int ind, int l, int r) {
    tree[ind] = tree[ind] + lazy[ind];
    if (l != r) {
      lazy[ind << 1] = lazy[ind << 1] + lazy[ind];
      lazy[ind << 1 | 1] = lazy[ind << 1 | 1] + lazy[ind];
    }
    lazy[ind] = inf;
  }
  
  void update(int x, int y, pair<int, int> val, int ind, int l, int r) {
    if (lazy[ind] != inf) down(ind, l, r);
    if (l > y || r < x) return;
    if (x <= l and r <= y) {
      lazy[ind] = val;
      down(ind, l, r);
      return;
    }
    int mid = (l + r) >> 1;
    update(x, y, val, ind << 1, l, mid);
    update(x, y, val, ind << 1 | 1, mid + 1, r);
    tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
  }

  pair<int, int> get(int x, int y, int ind, int l, int r) {
    if (lazy[ind] != inf) down(ind, l, r);
    if (l > y || r < x) return make_pair(1e9, 0);
    if (x <= l and r <= y) {
      return tree[ind];
    }
    int mid = (l + r) >> 1;
    return get(x, y, ind << 1, l, mid) + get(x, y, ind << 1 | 1, mid + 1, r);
  }
  
  void update(int x, int y, pair<int, int> val) { update(x, y, val, 1, 1, n); }
  pair<int, int> get(int x, int y) { return get(x, y, 1, 1, n); }
} st[LG + 1], sx;

void solve() {
  cin >> n >> k >> m;
  sx = segment_tree(n);
  for (int j = 0; j <= LG; ++j) {
    st[j] = segment_tree(n);
  }
  for (int i = 1; i <= n; ++i) {
    sx.update(i, i, make_pair(i, i));
  }
  for (int i = 1; i <= m; ++i) {
    int a, b; cin >> a >> b;
    if (a < b) {
      sx.update(a, min(b, a + k - 1), make_pair(b, b));
    } else {
      sx.update(max(b, a - k + 1), a, make_pair(b, b));
    }
  }
  for (int i = 1; i <= n; ++i) {
    pair<int, int> x = sx.get(i, i);
    st[0].update(i, i, x);
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      pair<int, int> x = st[j - 1].get(i, i);
      st[j].update(i, i, st[j - 1].get(x.first, x.second));
    }
  }
  int q; cin >> q;
  while (q--) {
    int l, r; cin >> l >> r;
    int res = 0; 
    pair<int, int> rg = make_pair(l, l);
    auto its = [&](pair<int, int> a, int x) {
      return a.first <= x and x <= a.second;
    };
    for (int i = LG; i >= 0; --i) {
      pair<int, int> tr = st[i].get(rg.first, rg.second);
      if (!its(tr, r)) {
        res |= (1 << i);
        rg = tr;
      }
    }
    rg = st[0].get(rg.first, rg.second);
    cout << (its(rg, r) ? res + 1 : -1) << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  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