제출 #1229771

#제출 시각아이디문제언어결과실행 시간메모리
1229771PenguinsAreCuteRailway Trip (JOI17_railway_trip)C++17
0 / 100
146 ms5412 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, k, q; cin >> n >> k >> q; vector<int> lvl(n); vector<int> adj[n]; for(int i=0;i<n;i++) cin >> lvl[i]; int lft[n], rgt[n]; stack<int> s; for(int i=0;i<n;i++) { while(s.size() && lvl[s.top()] < lvl[i]) s.pop(); lft[i] = (s.size()?s.top():-1); s.push(i); } while(s.size()) s.pop(); for(int i=n;i--;) { while(s.size() && lvl[s.top()] < lvl[i]) s.pop(); rgt[i] = (s.size()?s.top():-1); s.push(i); } vector<int> swp(n, 0); for(int i=0;i<n;i++) { if(rgt[i] != -1) { swp[i+1] ^= 1; swp[rgt[i]] ^= 1; } if(lft[i] != -1 && lvl[lft[i]] != lvl[i]) { swp[lft[i]+1] ^= 1; swp[i] ^= 1; } } partial_sum(swp.begin(),swp.end(),swp.begin()); auto cmp = [&lvl,&swp](int x, int y) -> bool { if(lvl[x] != lvl[y]) return lvl[x] < lvl[y]; if(swp[x] & 1) return x > y; return x < y; }; for(int i=0;i<n;i++) { if(lft[i] == -1 || cmp(lft[i], i)) lft[i] = rgt[i]; if(rgt[i] == -1 || cmp(rgt[i], i)) rgt[i] = lft[i]; if(lft[i] != -1 && cmp(rgt[i], lft[i])) swap(lft[i], rgt[i]); } int height[n]; memset(height,0,sizeof(height)); int ord[n]; iota(ord,ord+n,0); sort(ord,ord+n,cmp); for(int i=n-1;i--;) height[ord[i]] = height[lft[ord[i]]] + 1; while(q--) { int a, b, l; cin >> a >> b; a--; b--; int ans = 0; l = a; for(int c=a,d=b;c!=d;) { if(height[c] > height[d]) swap(c, d); l = d = lft[d]; } while(rgt[a] != -1 && height[l] <= height[rgt[a]]) a = rgt[a], ans++; while(rgt[b] != -1 && height[l] <= height[rgt[b]]) b = rgt[b], ans++; int dir = height[a] + height[b] - 2 * height[l]; int liftA = ~rgt[a] ? abs(height[rgt[a]] - height[b]) + 1 : 1e7; int liftB = ~rgt[b] ? abs(height[rgt[b]] - height[a]) + 1 : 1e7; int liftBoth = ~rgt[a] && ~rgt[b] ? abs(height[rgt[a]] - height[rgt[b]]) + 2 : 1e7; cout << ans + min({dir,liftA,liftB,liftBoth})-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...