Submission #1210075

#TimeUsernameProblemLanguageResultExecution timeMemory
1210075mychecksedadRailway Trip (JOI17_railway_trip)C++20
0 / 100
682 ms195916 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' #define ff first #define ss second #define pii pair<int,int> #define vi vector<int> #define cerr if(false) cerr const int N = 1e5+100, M = 1e5+10, K = 21, MX = 30; struct Fenwick{ vector<int> t; Fenwick(int n){ t.resize(n + 1); } void add(int v){ while(v < t.size()){ t[v]++; v += v & -v; } } int get(int v){ int res=0; while(v > 0){ res+=t[v]; v -= v&-v; } return res; } }; int n, k, q, a[N], d[N], rmq[N][K], rmq2[N][K], lazy[N]; vector<pii> g[N]; vector<pii> G[N]; vector<pii> A[N][21]; vector<int> ANS(N, MOD); vector<int> ANS2(N, MOD); vector<int> ANS3(N, MOD); vector<array<int, 3>> Q[N]; vector<array<int, 2>> Q1[N]; vector<array<int, 2>> Q2[N]; set<array<int, 2>> T[N]; int maxc(int x, int y){ return a[x] >= a[y] ? x : y; // left most } int maxc2(int x, int y){ return a[y] >= a[x] ? y : x; // right most } int get(int l, int r){ int k = int(log2(r-l+1)); return maxc(rmq[l][k], rmq[r-(1<<k)+1][k]); } int get2(int l, int r){ int k = int(log2(r-l+1)); return maxc2(rmq2[l][k], rmq2[r-(1<<k)+1][k]); } void add(int l, int r, int lev, int idx){ if(l > r) return; int L = 1, R = r, res = r; if(a[get(l, r)] < lev) return; while(L <= R){ int mid = L+R>>1; if(a[get(mid, r)] > lev){ L = mid + 1; }else{ res = mid; R = mid - 1; } } if(a[get(res, r)] == lev){ cerr << get2(res, r) << ' ' << idx << "f\n"; Q1[get2(res, r)].pb({idx, r+1}); } } void add2(int l, int r, int lev, int idx){ if(l > r) return; int L = l, R = r, res = l; if(a[get(l, r)] < lev) return; while(L <= R){ int mid = L+R>>1; if(a[get(l, mid)] > lev){ R = mid - 1; }else{ res = mid; L = mid + 1; } } if(a[get(l, res)] == lev){ Q2[get(l, res)].pb({idx, l-1}); } } void solve(){ cin >> n >> k >> q; vector<vi> C(k + 1); for(int i = 1; i <= n; ++i){ cin >> a[i]; C[a[i]].pb(i); rmq[i][0] = i; rmq2[i][0] = i; } for(int j = 1; j < K; ++j){ for(int i = 1; i + (1<<j) <= n + 1; ++i){ rmq[i][j] = maxc(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]); rmq2[i][j] = maxc2(rmq2[i][j-1], rmq2[i+(1<<(j-1))][j-1]); } } Fenwick fw(n); for(int i = k; i >= 1; --i){ for(int x: C[i]) fw.add(x); for(int j = 0; j < C[i].size(); ++j){ d[C[i][j]] = fw.get(C[i][j]); } } { vector<pii> Q; vector<int> W(n + 1); int w = 1; for(int i = 1; i <= n; ++i){ while(Q.size() && Q.back().ff <= a[i]) Q.pop_back(); if(Q.size()){ int v = i; int u = Q.back().ss; int last_pos = lower_bound(all(C[a[i]]), i) - C[a[i]].begin(); if(last_pos > 0 && C[a[i]][last_pos - 1] > u){ W[i] = W[C[a[i]][last_pos - 1]] + 1; }else{ W[i] = 1; } g[v].pb({u, W[i]}); G[u].pb({v, W[i]}); } Q.pb({a[i], i}); } Q.clear(); w = 1; for(int i = n; i >= 1; --i){ while(Q.size() && Q.back().ff <= a[i]) Q.pop_back(); if(Q.size()){ int v = i; int u = Q.back().ss; int last_pos = upper_bound(all(C[a[i]]), i) - C[a[i]].begin(); if(last_pos < C[a[i]].size() && C[a[i]][last_pos] < u){ W[i] = W[C[a[i]][last_pos]] + 1; }else{ W[i] = 1; } g[v].pb({u, W[i]}); G[u].pb({v, W[i]}); }else W[i] = 0; Q.pb({a[i], i}); } } // vector<bool> USED(n + 1); // for(int i = 1; i <= n; ++i){ // priority_queue<pair<int, int>> Q; // Q.push({0, i}); // vi use; // while(!Q.empty()){ // int v = Q.top().ss; // int cur = -Q.top().ff; // Q.pop(); // if(USED[v]) continue; // USED[v] = 1; // A[i][a[v]].pb({v, cur}); // use.pb(v); // for(auto [u, w_]: g[v]){ // Q.push({- cur - w_, u}); // } // } // for(int x: use) USED[x] = 0; // } for(int i = 1; i <= q; ++i){ int l, r; cin >> l >> r; if(l > r) swap(l, r); int ans = n; int level1 = get(l, r); int level2 = get2(l, r); Q1[level1].pb({i, l}); if(a[level1] > a[l]) add(1, l-1, a[level1], i); Q2[level2].pb({i, r}); if(a[level1] > a[r]) add2(r+1, n, a[level2], i); // cerr << l << ' ' << r << ' ' << level1 << " gg1\n"; // cerr << l << ' ' << r << ' ' << level2 << " gg2\n"; for(auto [node, W]: g[level1]){ // these nodes are same for level1 and level2 // cerr << l << ' ' << r << ' ' << node << " gg\n"; Q[node].pb({i, l, r}); } } vector<pii> pts; for(int i = 1; i <= n; ++i){ pts.pb({a[i], i}); lazy[i] = 0; } sort(all(pts)); vector<int> done(n + 1); for(int i = 1; i <= n; ++i){ done[i] = g[i].size(); } for(auto [_, v]: pts){ int big = -1; int ww = 0; for(auto [u, w]: G[v]){ if(big == -1 || T[u].size() > T[big].size()) big = u, ww = w; } if(big != -1){ if(done[big] == 1){ T[v].swap(T[big]); --done[big]; }else{ T[v] = T[big]; --done[big]; } lazy[v] = lazy[big] + ww; } T[v].insert({v, -lazy[v]}); for(auto [u, w]: G[v]){ if(u != big){ --done[u]; for(auto [node, dist]: T[u]){ auto it = T[v].lower_bound(array<int,2>{node, -MOD}); int nw = dist + lazy[u] + w - lazy[v]; if(it != T[v].end() && (*it)[0] == node){ if((*it)[1] > nw){ T[v].erase(it); T[v].insert({node, nw}); } }else{ T[v].insert({node, nw}); } } } } cerr << v << ' ' << lazy[v] << ":\n"; for(auto [pt, t]: T[v]){ cerr << pt << ' ' << t << '\n'; } for(auto [idx, pt]: Q1[v]){ auto it = T[v].lower_bound(array<int, 2>{pt, -MOD}); assert(it != T[v].end()); assert((*it)[0] == pt); ANS2[idx] = min(ANS2[idx], (*it)[1] + lazy[v] - d[v]); cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n'; } for(auto [idx, pt]: Q2[v]){ auto it = T[v].lower_bound(array<int, 2>{pt, -MOD}); assert(it != T[v].end()); assert((*it)[0] == pt); ANS3[idx] = min((*it)[1] + lazy[v] + d[v], ANS3[idx]); cerr << "# " << v << ' ' << idx << ' ' << pt << ' ' << (*it)[1] + lazy[v] << ' ' << d[v] << '\n'; } for(auto [idx, l, r]: Q[v]){ auto it = T[v].lower_bound(array<int, 2>{l, -MOD}); assert(it != T[v].end()); assert((*it)[0] == l); auto it2 = T[v].lower_bound(array<int, 2>{r, -MOD}); assert(it != T[v].end()); assert((*it2)[0] == r); ANS[idx] = min(ANS[idx], (*it)[1] + lazy[v] + (*it2)[1] + lazy[v]); } } for(int i = 1; i <= q; ++i){ // cout << ANS2[i] << ' ' << ANS3[i] << ' '; cout << min(ANS[i], ANS2[i] + ANS3[i]) - 1 << '\n'; } } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); en; } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...