Submission #1038144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038144		juicy	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	277 ms	233556 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 1e5 + 5, LG = 17;

int n, k, m, q;
int lg[N], a[2 * N], b[2 * N];
array<int, 2> spt[LG][LG][N], A[N];
vector<int> add[N], del[N];

array<int, 2> operator + (const array<int, 2> &a, const array<int, 2> &b) {
  return {min(a[0], b[0]), max(a[1], b[1])};
}

array<int, 2> qry(int k, int l, int r) {
  int f = lg[r - l + 1];
  return spt[k][f][l] + spt[k][f][r - (1 << f) + 1];
}

void init(array<int, 2> spt[LG][N]) {
  for (int i = 1; i <= n; ++i) {
    spt[0][i] = A[i];
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
      spt[j][i] = spt[j - 1][i] + spt[j - 1][i + (1 << j - 1)];
    }
  }
}

bool cov(const array<int, 2> &seg, int p) {
  return seg[0] <= p && p <= seg[1];
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> k >> m;
  for (int i = 2; i <= n; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int i = 1; i <= m; ++i) {
    cin >> a[i] >> b[i];
    if (a[i] < b[i]) {
      int r = min(a[i] + k - 1, b[i] - 1);
      add[r].push_back(b[i]);
      del[a[i]].push_back(b[i]);
    }
  }
  multiset<int> st;
  for (int i = n; i > 0; --i) {
    for (int x : add[i]) {
      st.insert(x);
    }
    A[i][1] = st.size() ? *st.rbegin() : i;
    for (int x : del[i]) {
      st.erase(st.find(x));
    }
  }
  for (int i = 1; i <= n; ++i) {
    add[i].clear();
    del[i].clear();
  }
  for (int i = 1; i <= m; ++i) {
    if (a[i] > b[i]) {
      int l = max(a[i] - k + 1, b[i] + 1);
      add[l].push_back(b[i]);
      del[a[i]].push_back(b[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    for (int x : add[i]) {
      st.insert(x);
    }
    A[i][0] = st.size() ? *st.begin() : i;
    for (int x : del[i]) {
      st.erase(st.find(x));
    }
  }
  init(spt[0]);
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i <= n; ++i) {
      A[i] = qry(j - 1, A[i][0], A[i][1]);
    }
    init(spt[j]);
  }
  cin >> q;
  while (q--) {
    int s, t; cin >> s >> t;
    array<int, 2> a{s, s};
    int res = 0;
    for (int j = LG - 1; ~j; --j) {
      auto x = qry(j, a[0], a[1]);
      if (!cov(x, t)) {
        a = x;
        res += 1 << j;
      }
    }
    a = qry(0, a[0], a[1]);
    cout << (cov(a, t) ? res + 1 : -1) << "\n";
  }
  return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void init(std::array<int, 2> (*)[100005])':
Main.cpp:33:58: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |       spt[j][i] = spt[j - 1][i] + spt[j - 1][i + (1 << j - 1)];
      |                                                        ~~^~~

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