Submission #1218445

#TimeUsernameProblemLanguageResultExecution timeMemory
1218445abczzRailway Trip (JOI17_railway_trip)C++20
100 / 100
473 ms116500 KiB
#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'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...