# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
335276 | 2020-12-11T19:25:58 Z | Plurm | Railway Trip (JOI17_railway_trip) | C++11 | 2000 ms | 13036 KB |
#include <bits/stdc++.h> using namespace std; vector<int> g[100005]; // cartesian-tree-like graph int d[100005]; vector<int> bckt[100005]; int l[100005]; int n,k,q; void compute(int a){ d[a] = 0; for(int i = 1; i <= k; i++){ for(int x : bckt[i]){ for(int y : g[x]) d[x] = min(d[x], d[y]+1); } reverse(bckt[i].begin(), bckt[i].end()); for(int x : bckt[i]){ for(int y : g[x]) d[x] = min(d[x], d[y]+1); } reverse(bckt[i].begin(), bckt[i].end()); } } int main(){ scanf("%d%d%d",&n,&k,&q); stack<int> stk; for(int i = 1; i <= n; i++){ scanf("%d", l+i); bckt[l[i]].push_back(i); while(!stk.empty() && l[stk.top()] <= l[i]){ g[i].push_back(stk.top()); stk.pop(); } if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top()); stk.push(i); } while(!stk.empty()) stk.pop(); for(int i = n; i > 0; i--){ while(!stk.empty() && l[stk.top()] <= l[i]){ g[i].push_back(stk.top()); stk.pop(); } if(!stk.empty() && l[stk.top()] == l[i]) g[i].push_back(stk.top()); stk.push(i); } while(q--){ int a,b; scanf("%d%d",&a,&b); memset(d, 0x3f, sizeof(d)); compute(a); vector<int> v(n); for(int i = 1; i <= n; i++) v[i] = d[i]; memset(d, 0x3f, sizeof(d)); compute(b); int ans = 1e9; for(int i = 1; i <= n; i++){ ans = min(ans, v[i] + d[i]); } printf("%d\n", ans-1); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 5376 KB | Output is correct |
2 | Correct | 5 ms | 5356 KB | Output is correct |
3 | Correct | 5 ms | 5356 KB | Output is correct |
4 | Correct | 6 ms | 5356 KB | Output is correct |
5 | Correct | 5 ms | 5356 KB | Output is correct |
6 | Correct | 6 ms | 5356 KB | Output is correct |
7 | Correct | 6 ms | 5356 KB | Output is correct |
8 | Correct | 6 ms | 5356 KB | Output is correct |
9 | Runtime error | 11 ms | 10872 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 8 ms | 5484 KB | Output is correct |
2 | Correct | 426 ms | 9440 KB | Output is correct |
3 | Correct | 462 ms | 9456 KB | Output is correct |
4 | Correct | 546 ms | 9324 KB | Output is correct |
5 | Correct | 552 ms | 9452 KB | Output is correct |
6 | Correct | 564 ms | 9572 KB | Output is correct |
7 | Correct | 1205 ms | 11116 KB | Output is correct |
8 | Correct | 185 ms | 9956 KB | Output is correct |
9 | Correct | 196 ms | 10988 KB | Output is correct |
10 | Correct | 163 ms | 10472 KB | Output is correct |
11 | Correct | 474 ms | 10596 KB | Output is correct |
12 | Correct | 478 ms | 10348 KB | Output is correct |
13 | Correct | 465 ms | 10212 KB | Output is correct |
14 | Correct | 509 ms | 10596 KB | Output is correct |
15 | Correct | 454 ms | 10348 KB | Output is correct |
16 | Correct | 495 ms | 10092 KB | Output is correct |
17 | Correct | 486 ms | 9700 KB | Output is correct |
18 | Correct | 483 ms | 9708 KB | Output is correct |
19 | Correct | 374 ms | 13036 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2098 ms | 9452 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2085 ms | 11364 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |