Submission #1032976

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032976		NeroZein	Railway Trip 2 (JOI22_ho_t4)	C++17	100 / 100	607 ms	79044 KiB

Main

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

#ifdef Nero
#include "Deb.h"
#else
#define debug(...)
#endif

const int LOG = 18; 
const int N = 1e5 + 5; 

struct segtree {
  struct node {
    int mn = 0, mx = 0; 
  };
  int n; 
  vector<node> seg;
  void init (vector<int>& a) {
    n = (int) a.size();
    seg.resize(2 * n - 1); 
    build(0, 0, n - 1, a); 
  }
  node combine(node lx, node rx) {
    node ret;
    ret.mn = min(lx.mn, rx.mn);
    ret.mx = max(lx.mx, rx.mx); 
    return ret; 
  }
  void build(int nd, int l, int r, vector<int>& a) {
    if (l == r) {
      seg[nd].mn = seg[nd].mx = a[l];
      return;
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    build(nd + 1, l, mid, a);
    build(rs, mid + 1, r, a); 
    seg[nd] = combine(seg[nd + 1], seg[rs]); 
  }
  node qry(int nd, int l, int r, int s, int e) {
    if (l >= s && r <= e) {
      return seg[nd];
    }
    int mid = (l + r) >> 1;
    int rs = nd + ((mid - l + 1) << 1);
    if (mid >= e) {
      return qry(nd + 1, l, mid, s, e);
    } else {
      if (mid < s) {
        return qry(rs, mid + 1, r, s, e);
      } else {
        return combine(qry(nd + 1, l, mid, s, e), qry(rs, mid + 1, r, s, e));
      }
    }
  }
  int get_min(int l, int r) {
    return qry(0, 0, n - 1, l, r).mn;
  }
  int get_max(int l, int r) {
    return qry(0, 0, n - 1, l, r).mx; 
  }
};

bool contain(int l, int r, int x) {
  return l <= x && x <= r;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, k, m;
  cin >> n >> k >> m;
  vector<int> min_left_edge(n + 1);
  vector<int> max_right_edge(n + 1); 
  for (int i = 1; i <= n; ++i) {
    min_left_edge[i] = max_right_edge[i] = i; 
  }
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v;
    if (u > v) {
      min_left_edge[u] = min(min_left_edge[u], v);
    } else {
      max_right_edge[u] = max(max_right_edge[u], v);
    }
  }
  multiset<int> se; 
  vector<vector<int>> max_right(LOG, vector<int>(n + 1));
  for (int i = 1; i <= n; ++i) {
    if (i - k > 0) {
      se.erase(se.find(max_right_edge[i - k]));
    }
    se.insert(max_right_edge[i]);
    max_right[0][i] = *se.rbegin();
  }
  se.clear();
  vector<vector<int>> min_left(LOG, vector<int>(n + 1));
  for (int i = n; i >= 1; --i) {
    if (i + k <= n) {
      se.erase(se.find(min_left_edge[i + k]));
    }
    se.insert(min_left_edge[i]);
    min_left[0][i] = *se.begin();
    //debug(i, min_left[0][i]);
  }
  vector<segtree> rmn(LOG), rmx(LOG);
  rmn[0].init(min_left[0]);
  rmx[0].init(max_right[0]); 
  for (int j = 1; j < LOG; ++j) {
    for (int i = 1; i <= n; ++i) {
      int l = min_left[j - 1][i], r = max_right[j - 1][i];
      if (l > r) {
        min_left[j][i] = l;
        max_right[j][i] = r; 
      } else {
        min_left[j][i] = rmn[j - 1].get_min(l, r);
        max_right[j][i] = rmx[j - 1].get_max(l, r);         
      }
    }
    rmn[j].init(min_left[j]);
    rmx[j].init(max_right[j]);
  }
  int q;
  cin >> q;
  while (q--) {
    int s, t;
    cin >> s >> t;
    int l = s, r = s; 
    int ans = 0; 
    for (int j = LOG - 1; j >= 0; --j) {
      int nl = rmn[j].get_min(l, r);
      int nr = rmx[j].get_max(l, r);
      //debug(l, r, nl, nr); 
      if (!contain(nl, nr, t)) {
        ans += 1 << j;
        l = nl;
        r = nr; 
      }
    }
    if (ans == (1 << LOG) - 1) {
      cout << -1 << '\n';
    } else {
      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