#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
const int K = 1;
using namespace std;
typedef long long ll;
const ll inf = 8e18;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n, m = 0;
ll t;
cin >> n >> t;
vector<vector<pair<int, int>>> rngs(n);
vector<int> sz(n), pre(n);
for(int i = 1; i < n; i++){
int tmp;
cin >> tmp;
for(int j = 0; j < tmp; j++){
int a, b;
cin >> a >> b;
rngs[i].emplace_back(a, b);
}
sort(rngs[i].begin(), rngs[i].end());
vector<pair<int, int>> vtmp;
int mini = 2e9;
for(int j = tmp - 1; j >= 0; j--){
auto x = rngs[i][j];
if(x.second < mini){
mini = x.second;
vtmp.push_back(x);
}
}
reverse(vtmp.begin(), vtmp.end());
rngs[i] = vtmp;
sz[i] = (int)rngs[i].size();
m += sz[i];
pre[i] = pre[i - 1] + sz[i];
}
vector<vector<pair<int, ll>>> panc(17, vector<pair<int, ll>>(m + 1)), nanc(17, vector<pair<int, ll>>(m + 1));
vector<pair<int, ll>> lst(m + 1), nxt(m + 1);
for(int i = 2; i < n; i++){
int ptr = 0;
for(int j = 0; j < sz[i - 1]; j++){
int id = pre[i - 2] + j + 1;
while(ptr < sz[i] && rngs[i][ptr].first < rngs[i - 1][j].second) ptr++;
if(ptr < sz[i]) nxt[id] = make_pair(pre[i - 1] + ptr + 1, rngs[i][ptr].first - rngs[i - 1][j].second);
else nxt[id] = make_pair(pre[i - 1] + 1, t + rngs[i][0].first - rngs[i - 1][j].second);
}
ptr = -1;
for(int j = 0; j < sz[i]; j++){
int id = pre[i - 1] + j + 1;
while(ptr < sz[i - 1] - 1 && rngs[i - 1][ptr + 1].second <= rngs[i][j].first) ptr++;
if(ptr >= 0) lst[id] = make_pair(pre[i - 2] + ptr + 1, rngs[i][j].first - rngs[i - 1][ptr].second);
else lst[id] = make_pair(pre[i - 1], t + rngs[i][j].first - rngs[i - 1][sz[i - 1] - 1].second);
}
}
for(int i = 1; i < n; i++){
for(int j = 0; j < sz[i]; j++){
int id = pre[i - 1] + j + 1;
nanc[0][id] = make_pair(id, rngs[i][j].second - rngs[i][j].first);
panc[0][id] = nanc[0][id];
}
}
for(int i = 1; i < 17; i++){
for(int j = 1; j <= m; j++){
nanc[i][j] = make_pair(nanc[i - 1][nxt[nanc[i - 1][j].first].first].first, nanc[i - 1][j].second + nanc[i - 1][nxt[nanc[i - 1][j].first].first].second + nxt[nanc[i - 1][j].first].second);
panc[i][j] = make_pair(panc[i - 1][lst[panc[i - 1][j].first].first].first, panc[i - 1][j].second + panc[i - 1][lst[panc[i - 1][j].first].first].second + lst[panc[i - 1][j].first].second);
}
}
auto nquery = [&](int pos, int kk, int k2){
ll mini = inf;
for(int times = 0; times < sz[pos]; times++){
int id = pre[pos - 1] + times + 1;
ll ans = -rngs[pos][times].second + rngs[pos][times].first;
int k = kk;
for(int i = 0; i < 17; i++){
if(k & (1 << i)){
k -= (1 << i);
ans += nanc[i][id].second;
id = nanc[i][id].first;
if(k > 0) ans += nxt[id].second;
id = nxt[id].first;
//cout << id << " " << ans << "\n";
}
}
//cout << ans << "\n";
id = pre[pos - 1] + times + 1;
k = k2;
for(int i = 0; i < 17; i++){
if(k & (1 << i)){
k -= (1 << i);
ans += panc[i][id].second;
id = panc[i][id].first;
if(k > 0) ans += lst[id].second;
id = lst[id].first;
}
}
mini = min(mini, ans);
}
return mini;
};
vector<vector<pair<int, int>>> st(17, vector<pair<int, int>>(n));
for(int j = 1; j < n; j++){
st[0][j] = make_pair(sz[j], j);
}
for(int i = 1; i < 17; i++) for(int j = 1; j < n; j++) st[i][j] = min(st[i - 1][j], st[i - 1][min(n - 1, j + (1 << (i - 1)))]);
vector<int> bases(n);
for(int i = 1; i < n; i++){
bases[i] = bases[i - 1];
if(i == (1 << (bases[i] + 1))) bases[i]++;
}
auto query = [&](int l, int r){
r--;
int len = r - l + 1;
return min(st[bases[len]][l], st[bases[len]][r - (1 << bases[len]) + 1]).second;
};
int q;
cin >> q;
vector<ll> anss(q);
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
if(r - l > K){
int best = query(l, r);
cout << nquery(best, r - best, best - l + 1) << "\n";
//cout << best << "\n";
}
}
//for(int i = 1; i <= m; i++) cout << nanc[1][i].first << " " << nanc[1][i].second << '\n';
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run escape.cpp
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
3920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
3920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
3920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
3920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Incorrect |
937 ms |
56284 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Incorrect |
22 ms |
3920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
