| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1162473 | tw20000807 | Road Closures (APIO21_roads) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
struct TABLE{
int n;
int g;
vector< vector< int > > dp;
TABLE(){}
TABLE(vector< int > &v){
n = SZ(v);
g = __lg(n) + 1;
dp.resize(g, vector< int >(n));
for(int i = 0; i < n; ++i){
dp[0][i] = v[i];
}
for(int j = 1; j < g; ++j){
for(int i = 0; i + (1 << j) - 1 < n; ++i){
dp[j][i] = min(dp[j - 1][i], dp[j - 1][i + (1 << (j - 1))]);
}
}
}
int query(int l, int r){
int lg = __lg(r - l + 1);
return min(dp[lg][l], dp[lg][r - (1 << lg) + 1]);
}
};
vector< TABLE > mn;
vector< vector< int > > dis;
void init(int n, vector<int> h) {
vector< int > l(n, -1), r(n, -1);
for(int i = 0; i < n; ++i) cin >> h[i];
{
vector< int > stk;
for(int i = 0; i < n; ++i){
while(!stk.empty() && h[stk.back()] < h[i]){
r[stk.back()] = i;
stk.pop_back();
}
l[i] = stk.empty() ? -1 : stk.back();
stk.push_back(i);
}
}
// for(int i = 0; i < n; ++i) cerr << l[i] << " " << r[i] << "--\n";
auto f = [&](vector< int > &dis, int s) -> void {
vector< int > dq{s};
dis[s] = 0;
dq.push_back(s);
int id = 0;
while(id < SZ(dq)){
int cur = dq[id++];
for(auto nxt : {l[cur], r[cur]}) if(nxt != -1) {
if(dis[nxt] > dis[cur] + 1){
dis[nxt] = dis[cur] + 1;
dq.push_back(nxt);
}
}
}
};
dis.resize(n, vector< int >(n, 1e9));
mn.resize(n);
for(int i = 0; i < n; ++i){
f(dis[i], i);
mn[i] = TABLE(dis[i]);
}
}
int minimum_jumps(int a, int b, int c, int d) {
int ans = 1e9;
for(int i = a; i <= b; ++i){
ans = min(ans, mn[i].query(c, d));
}
if(ans == 1e9) return -1;
else return ans;
}