#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = numeric_limits<ll> :: max();
const int M = 1e5;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, D; cin>>n>>D;
vector<int> x(n);
vector<pii> t[n];
for (int i = 1; i < n; i++){
cin>>x[i];
for (int j = 0; j < x[i]; j++){
int a, b; cin>>a>>b;
t[i].pb({a, b});
}
}
for (int i = 1; i < n; i++){
sort(t[i].begin(), t[i].end());
vector<pii> nw;
for (int j = 0; j < x[i]; j++){
while (!nw.empty() && nw.back().ss >= t[i][j].ss){
nw.pop_back();
}
if (nw.empty() || nw.back().ff != t[i][j].ff){
nw.pb(t[i][j]);
}
}
t[i] = nw;
x[i] = (int) t[i].size();
}
vector<int> p(n);
for (int i = 1; i < n; i++){
p[i] = p[i - 1] + x[i];
}
int S = p.back();
vector<int> g(S);
vector<bool> e(S);
for (int i = 1; i + 1 < n; i++){
int k = x[i + 1] - 1, mn = 0;
for (int j = x[i] - 1; j >= 0; j--){
while (k >= 0 && t[i + 1][k].ff >= t[i][j].ss){
mn = k--;
}
g[p[i - 1] + j] = p[i] + mn;
e[p[i - 1] + j] = (t[i][j].ss > t[i + 1][mn].ff);
}
}
const int lg = log2(S);
pii sp[S][lg + 1];
for (int i = 0; i < S; i++) sp[i][0] = {g[i], e[i]};
for (int j = 1; j <= lg; j++){
for (int i = 0; i + (1 << j) <= S; i++){
sp[i][j] = {sp[sp[i][j - 1].ff][j - 1].ff, sp[i][j - 1].ss + sp[sp[i][j - 1].ff][j - 1].ss};
}
}
auto get = [&](int l, int r){
ll out = inf;
for (int i = 0; i < x[l]; i++){
int tt = r - l - 1, f = p[l - 1] + i, cc = 0;
for (int j = lg; j >= 0; j--){
int k = (1 << j);
if (tt >= k){
cc += sp[f][j].ss;
f = sp[f][j].ff;
tt -= k;
}
}
out = min(out, 1LL * D * cc + (t[r - 1][f - p[r - 2]].ss - t[l][i].ff));
}
return out;
};
const int A = 500;
vector<int> all;
pair<int, ll> st[M], nw[M];
ll out[M / A + 5][n + 1];
int s1 = 0, s2 = 0, cc = 0;
ll mn;
for (int i = 1; i < n; i++){
if (x[i] <= A) continue;
all.pb(i);
s1 = s2 = 0;
for (int j = 0; j < x[i]; j++){
st[s1++] = {p[i - 1] + j, t[i][j].ss - t[i][j].ff};
}
for (int j = i + 1; j <= n; j++){
mn = inf;
for (int k = 0; k < s1; k++){
mn = min(mn, st[k].ss);
}
out[cc][j] = mn;
if (j == n) break;
for (int k = 0; k < s1; k++){
auto &[x, y] = st[k];
y += D * e[x] + (t[j][g[x] - p[j - 1]].ss - t[j - 1][x - p[j - 2]].ss);
x = g[x];
}
s2 = 0;
int k = 0;
while (k < s1){
int h = k; mn = inf;
while (h < s1 && st[k].ff == st[h].ff){
mn = min(mn, st[h].ss);
h++;
}
nw[s2++] = {st[k].ff, mn};
k = h;
}
s1 = s2;
for (int i = 0; i < s1; i++){
st[i] = nw[i];
}
}
cc++;
}
vector<int> :: iterator it;
int q; cin>>q;
for (int i = 1; i <= q; i++){
int l, r; cin>>l>>r;
if (x[l] <= A){
cout<<get(l, r)<<"\n";
}
else {
it = lower_bound(all.begin(), all.end(), l);
int j = (int) (it - all.begin());
cout<<out[j][r]<<"\n";
}
}
}
Compilation message
Main.cpp: In lambda function:
Main.cpp:79:27: sorry, unimplemented: capture of variably-modified type 'pii [S][(((int)lg) + 1)]' {aka 'std::pair<int, int> [S][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
79 | cc += sp[f][j].ss;
| ^~
Main.cpp:79:27: note: because the array element type 'pii [(((int)lg) + 1)]' {aka 'std::pair<int, int> [(((int)lg) + 1)]'} has variable size
Main.cpp:80:25: sorry, unimplemented: capture of variably-modified type 'pii [S][(((int)lg) + 1)]' {aka 'std::pair<int, int> [S][(((int)lg) + 1)]'} that is not an N3639 array of runtime bound
80 | f = sp[f][j].ff;
| ^~
Main.cpp:80:25: note: because the array element type 'pii [(((int)lg) + 1)]' {aka 'std::pair<int, int> [(((int)lg) + 1)]'} has variable size
