Submission #1218445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218445		abczz	Railway Trip (JOI17_railway_trip)	C++20	100 / 100	473 ms	116500 KiB

railway_trip

#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

ll bl[100000][18], bl_left[100000][18], bl_right[100000][18], ps[100000][18];
array <ll, 2> hash_left[100000][18], hash_right[100000][18];
ll n, k, q, a, b, A[100000];
ll MOD1 = 1e9 + 9, MOD2 = 1e9 + 11, P1 = 100003, P2 = 100153;
array <ll, 2> operator+ (array<ll, 2> a, array<ll, 2> b) {return {(a[0]+b[0]) % MOD1, (a[1]+b[1]) % MOD2};}
array <ll, 2> operator* (array<ll, 2> a, array<ll, 2> b) {return {(a[0]*b[0]) % MOD1, (a[1]*b[1]) % MOD2};}

array <ll, 2> P[18];
struct SegTree{
  ll st[400000];
  void build(ll id, ll l, ll r) {
    if (l == r) {
      st[id] = A[l];
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query_max(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return -1;
    ll mid = (l+r)/2;
    if (ql <= l && r <= qr) {
      if (l == r) return l;
      if (st[id*2] >= st[id*2+1]) return query_max(id*2, l, mid, ql, qr);
      else return query_max(id*2+1, mid+1, r, ql, qr);
    }
    ll u = query_max(id*2, l, mid, ql, qr), v = query_max(id*2+1, mid+1, r, ql, qr);
    if (u == -1) return v;
    if (v == -1) return u;
    return (A[u] >= A[v] ? u : v);
  }
  ll query_left(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || st[id] < w || ql > qr) return -1;
    ll mid = (l+r)/2;
    if (ql <= l && r <= qr) {
      if (l == r) return l;
      if (st[id*2+1] >= w) return query_left(id*2+1, mid+1, r, ql, qr, w);
      else return query_left(id*2, l, mid, ql, qr, w);
    }
    ll u = query_left(id*2+1, mid+1, r, ql, qr, w);
    return (u != -1 ? u : query_left(id*2, l, mid, ql, qr, w));
  }
  ll query_right(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql || st[id] < w || ql > qr) return -1;
    ll mid = (l+r)/2;
    if (ql <= l && r <= qr) {
      if (l == r) return l;
      if (st[id*2] >= w) return query_right(id*2, l, mid, ql, qr, w);
      else return query_right(id*2+1, mid+1, r, ql, qr, w);
    }
    ll u = query_right(id*2, l, mid, ql, qr, w);
    return (u != -1 ? u : query_right(id*2+1, mid+1, r, ql, qr, w));
  }
}ST;
ll move(ll x, ll y) {
  ll res = 0;
  for (int j=17; j>=0; --j) {
    if (x < y && bl_right[x][j] < y) {
      x = bl_right[x][j], res += (1LL<<j);
    }
    else if (x > y && bl_left[x][j] > y) {
      x = bl_left[x][j], res += (1LL<<j);
    }
  }
  if (x != y) ++res;
  return res;
}
ll dist(ll x, ll y) {
  if (y == -1) return 1e18;
  ll res = 0;
  for (int j=17; j>=0; --j) {
    if (A[bl[x][j]] <= A[y]) {
      res += ps[x][j];
      x = bl[x][j];
    }
  }
  if (x == y) return res;
  res += move(x, y);
  return res;
}
int main() {
  P[0][0] = P1, P[0][1] = P2;
  cin >> n >> k >> q;
  for (int i=0; i<n; ++i) {
    cin >> A[i];
    --A[i];
  }
  ST.build(1, 0, n-1);
  for (int i=0; i<n; ++i) {
    auto u = ST.query_left(1, 0, n-1, 0, i-1, A[i]);
    bl_left[i][0] = (u == -1 ? i : u);
    auto v = ST.query_right(1, 0, n-1, i+1, n-1, A[i]);
    bl_right[i][0] = (v == -1 ? i : v);
    hash_left[i][0] = hash_right[i][0] = {A[i]+1, A[i]+1};
  }
  for (int j=1; j<18; ++j) {
    P[j][0] = (P[j-1][0] * P[j-1][0]) % MOD1;
    P[j][1] = (P[j-1][1] * P[j-1][1]) % MOD2;
    for (int i=0; i<n; ++i) {
      bl_left[i][j] = bl_left[bl_left[i][j-1]][j-1], bl_right[i][j] = bl_right[bl_right[i][j-1]][j-1];
      hash_left[i][j] = hash_left[i][j-1] + (bl_left[i][j] == bl_left[i][j-1] ? array<ll, 2>{0, 0} : hash_left[bl_left[i][j-1]][j-1] * P[j-1]);
      hash_right[i][j] = hash_right[i][j-1] + (bl_right[i][j] == bl_right[i][j-1] ? array<ll, 2>{0, 0} : hash_right[bl_right[i][j-1]][j-1] * P[j-1]);
    }
  }
  for (int i=0; i<n; ++i) {
    if (bl_left[i][0] == i || bl_right[i][0] == i) {
      bl[i][0] = i;
      continue;
    }
    ll u = i, v = i;
    for (int j=17; j>=0; --j) {
      if (hash_left[u][j] == hash_right[v][j]) u = bl_left[u][j], v = bl_right[v][j];
    }
    if (A[u] == A[v]) bl[i][0] = i;
    else if (A[u] < A[v]) bl[i][0] = v, ps[i][0] = move(i, v);
    else bl[i][0] = u, ps[i][0] = move(i, u);
  }
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
      ps[i][j] = ps[i][j-1] + ps[bl[i][j-1]][j-1];
    }
  }
  for (int i=0; i<q; ++i) {
    cin >> a >> b;
    --a, --b;
    if (a > b) swap(a, b);
    auto u = ST.query_max(1, 0, n-1, a, b);
    auto x = ST.query_left(1, 0, n-1, 0, a-1, A[u]+1);
    auto y = ST.query_right(1, 0, n-1, b+1, n-1, A[u]+1);
    cout << min(dist(a, u)+dist(b, u), min(dist(a, x)+dist(b, x), dist(a, y)+dist(b, y)))-1 << '\n';
  }
}

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 55 / 55