| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 55058 | ksun48 | Railway Trip (JOI17_railway_trip) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int next[2][100000][20]; // next stop of level <= j, you are <= j+1 (taking trains of j+1)
int idx[100000][21];
int main(){
int n, k, q;
cin >> n >> k >> q;
vector<int> level(n);
for(int i = 0; i < n; i++){
cin >> level[i];
level[i] = k - level[i];
}
vector<pair<int,int> > queries;
for(int i = 0; i < q; i++){
int a, b;
cin >> a >> b;
a--; b--;
queries.push_back({a,b});
}
for(int j = 0; j <= k; j++){
int cur = 0;
for(int i = 0; i < n; i++){
if(level[i] <= j){
idx[i][j] = cur;
cur++;
}
}
}
for(int j = 0; j < k; j++){
int prev = 0;
for(int i = 0; i < n; i++){
if(level[i] > j+1) continue;
if(level[i] <= j){
prev = i;
}
next[0][i][j] = prev;
}
prev = n-1;
for(int i = n-1; i >= 0; i--){
if(level[i] > j+1) continue;
if(level[i] <= j){
prev = i;
}
next[1][i][j] = prev;
}
}
for(int zz = 0; zz < queries.size(); zz++){
vector<pair<int,int> > stuff[2]; // loc, dist
stuff[0].push_back({queries[zz].first, 0});
stuff[1].push_back({queries[zz].second, 0});
int ans = 1000000000;
for(int j = k-1; j >= 0; j--){
// go to level j
for(int p = 0; p < 2; p++){
vector<pair<int,int> > newstuff;
for(pair<int,int> x : stuff[p]){
// go left from x, go right from x;
int loc = x.first;
int dist = x.second;
for(int dir = 0; dir < 2; dir++){
int newloc = next[dir][loc][j];
int newdist = dist + abs(idx[ loc ][j+1] - idx[ newloc ][j+1]);
newstuff.push_back({newloc, newdist});
}
}
int a = 0;
while(a + 1 < newstuff.size()){
if(newstuff[a].first == newstuff[a+1].first){
newstuff[a].second = min(newstuff[a].second, newstuff[a+1].second);
newstuff.erase(newstuff.begin() + a + 1);
}
a++;
}
stuff[p] = newstuff;
}
// find ans
for(pair<int,int> x0 : stuff[0]){
for(pair<int,int> x1 : stuff[1]){
ans = min(ans, x0.second + x1.second + abs(idx[x0.first][j] - idx[x1.first][j]));
}
}
}
cout << ans - 1 << '\n';
}
}