Submission #1303542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303542		julia_08	Railway Trip 2 (JOI22_ho_t4)	C++20	100 / 100	628 ms	68116 KiB

Main

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

const int MAXN = 2e5 + 10;

struct node{
  int min, max;
};

int l[20][MAXN], r[20][MAXN];

node seg[20][4 * MAXN];

int n;

node merge(node a, node b){
  return {
    min(a.min, b.min),
    max(a.max, b.max)
  };
}

void build(int x, int lx, int rx, int k){

  if(lx == rx){
    seg[k][x] = {l[k][lx], r[k][rx]};
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  build(lc, lx, m, k);
  build(rc, m + 1, rx, k);

  seg[k][x] = merge(seg[k][lc], seg[k][rc]);

}

node query(int x, int lx, int rx, int l, int r, int k){

  if(rx < l || lx > r) return {n, 1};

  if(l <= lx && rx <= r) return seg[k][x];

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;
  return merge(query(lc, lx, m, l, r, k), query(rc, m + 1, rx, l, r, k));

}

int query(int s, int t){

  int cur_l = s, cur_r = s;

  int ans = 0;

  for(int k=19; k>=0; k--){

    auto [new_l, new_r] = query(1, 1, n, cur_l, cur_r, k);

    if(t < new_l || t > new_r){

      cur_l = new_l;
      cur_r = new_r;

      ans += (1 << k);

    } 
  
  }

  auto [new_l, new_r] = query(1, 1, n, cur_l, cur_r, 0);

  if(t < new_l || t > new_r) return -1;
  return ans + 1;

}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int k; cin >> n >> k;

  for(int i=1; i<=n; i++) l[0][i] = r[0][i] = i;

  int m; cin >> m;

  vector<pair<int, pair<int, int>>> all_events; 

  while(m--){

    int a, b; cin >> a >> b;

    int x, y;

    if(a < b){

      x = a; 
      y = min(b, a + k - 1);

    } else{

      y = a;
      x = max(b, a - k + 1);

    }

    all_events.push_back({x, {-1, b}});
    all_events.push_back({y, {1, b}});

  }

  for(int i=1; i<=n; i++) all_events.push_back({i, {0, i}});

  sort(all_events.begin(), all_events.end());
  
  multiset<int> ms;

  for(auto ev : all_events){

    int x = ev.first;
    auto [t, b] = ev.second;

    if(t == -1){

      ms.insert(b);

    } else if(t == 0){

      if(ms.empty()) continue;

      l[0][x] = min(l[0][x], *ms.begin());
      r[0][x] = max(r[0][x], *ms.rbegin());

    } else ms.erase(ms.find(b));

  }

  build(1, 1, n, 0);

  for(int k=1; k<20; k++){

    for(int i=1; i<=n; i++){
      
      node ans = query(1, 1, n, l[k - 1][i], r[k - 1][i], k - 1);

      l[k][i] = ans.min;
      r[k][i] = ans.max;

    }

    build(1, 1, n, k);

  }

  int q; cin >> q;

  while(q--){
    int s, t; cin >> s >> t;
    cout << query(s, t) << "\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