#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define ar array
#define pb push_back
#define ln '\n'
//~ #define int long long
using i64 = long long;
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
const i64 inf = 1e15;
const int H = 18;
int T;
struct func{
// messy struct
vector <int> m, b;
vector <vector<ar<int,2>>> a;
vector <vector<int>> id, up, w;
vector <ar<int,2>> rev;
int n, ct;
void modify(auto a_){
a = a_, n = a.size();
m.resize(n); id.resize(n);
ct = 0;
for ( int i = 0; i + 1 < n; i++ ){
m[i] = a[i].size();
id[i].resize(m[i]);
for ( auto &u: id[i] ) u = ct++;
}
rev.resize(ct);
b.resize(ct);
for ( int i = 0; i + 1 < n; i++ ){
for ( int j = 0; j < m[i]; j++ ){
rev[id[i][j]] = a[i][j];
b[id[i][j]] = i;
}
}
up.resize(ct);
w.resize(ct);
for ( int i = 0; i < ct; i++ ){
up[i].resize(H, -1);
w[i].resize(H);
}
for ( int i = 0; i + 2 < n; i++ ){
vector <ar<int,3>> q;
for ( int k = 0; k < m[i + 1]; k++ ){
auto [x, y] = a[i + 1][k];
q.pb({-x, y, k});
}
sort(all(q));
set <pair<int,int>> st;
int mn = 2e9;
for ( auto [x, y, k]: q ){
if ( y >= mn ) continue;
st.insert({-x, k});
mn = y;
}
for ( int j = 0; j < m[i]; j++ ){
auto [l, r] = a[i][j];
ar <int,3> opt;
auto it = st.lower_bound({r, -1});
if ( it != st.end() ){
opt = {0, a[i + 1][it -> second][1], it -> second};
} else{
int k = st.begin() -> second;
opt = {1, a[i + 1][k][1], k};
}
up[id[i][j]][0] = id[i + 1][opt[2]];
w[id[i][j]][0] = opt[0];
}
}
for ( int j = 1; j < H; j++ ){
for ( int i = 0; i < ct; i++ ){
if ( up[i][j - 1] == -1 ){
up[i][j] = up[i][j - 1];
w[i][j] = w[i][j - 1];
} else{
up[i][j] = up[up[i][j - 1]][j - 1];
w[i][j] = w[i][j - 1] + w[up[i][j - 1]][j - 1];
}
}
}
}
i64 get(int u, int r){
i64 cnt = 0;
for ( int i = H - 1; i >= 0; i-- ){
if ( up[u][i] == -1 ){
continue;
}
if ( b[up[u][i]] < r ){
cnt += w[u][i];
u = up[u][i];
}
}
cnt = cnt * T + rev[u][1];
return cnt;
}
i64 qry(int l, int r){
i64 opt = inf;
for ( int j = 0; j < m[l]; j++ ){
auto [x, y] = a[l][j];
chmin(opt, get(id[l][j], r) - x);
}
return opt;
}
auto RunDjk(int sx){
vector <i64> dp(ct, inf);
priority_queue <ar<i64,2>> q;
for ( int i = 0; i < m[sx]; i++ ){
dp[id[sx][i]] = a[sx][i][1] - a[sx][i][0];
q.push({-dp[id[sx][i]], id[sx][i]});
}
all I need is a love tonight is
while ( !q.empty() ){
auto [val, u] = q.top();
q.pop();
if ( -val != dp[u] ) continue;
if ( up[u][0] != -1 ){
int nxt = up[u][0];
i64 cost = -val + (w[u][0] ? T - rev[u][1] + rev[nxt][1] : rev[nxt][1] - rev[u][1]);
if ( chmin(dp[nxt], cost) ){
q.push({-cost, nxt});
}
}
}
vector <i64> f(n, inf);
for ( int i = 0; i < ct; i++ ){
chmin(f[b[i] + 1], dp[i]);
}
return f;
}
};
const int B = 1000;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n >> T;
vector <vector<ar<int,2>>> a(n);
vector <int> m(n);
for ( int i = 0; i + 1 < n; i++ ){
cin >> m[i];
a[i].resize(m[i]);
for ( auto &[l, r]: a[i] ){
cin >> l >> r;
}
}
func lf; lf.modify(a);
int q; cin >> q;
vector <vector<ar<int,2>>> qu(n);
for ( int i = 0; i < q; i++ ){
int l, r; cin >> l >> r;
--l, --r;
qu[l].pb({i, r});
}
vector <i64> ans(q, inf);
for ( int i = 0; i + 1 < n; i++ ){
if ( m[i] < B ){
for ( auto &[j, r]: qu[i] ){
ans[j] = lf.qry(i, r);
}
}
auto bst = lf.RunDjk(i);
for ( auto &[j, r]: qu[i] ){
ans[j] = bst[r];
}
}
for ( auto &x: ans ){
cout << x << ln;
}
cout << '\n';
}
Compilation message
Main.cpp:47:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
47 | void modify(auto a_){
| ^~~~
Main.cpp: In member function 'auto func::RunDjk(int)':
Main.cpp:173:3: error: 'all' was not declared in this scope; did you mean 'std::filesystem::perms::all'?
173 | all I need is a love tonight is
| ^~~
| std::filesystem::perms::all
In file included from /usr/include/c++/10/filesystem:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
from Main.cpp:1:
/usr/include/c++/10/bits/fs_fwd.h:148:7: note: 'std::filesystem::perms::all' declared here
148 | all = 0777,
| ^~~
