#include<bits/stdc++.h>
const int L = 17;
using namespace std;
void solve(){
int n, t, r;cin >> n >> t;
set<pair<int, int>> s[n-1];
vector<pair<int, int>> pp[n-1];
for(int i = 0;i < n-1;i++){
cin >> r;
while(r--){
int a, b;cin >> a >> b;
if(s[i].empty() || s[i].rbegin()->first<a || s[i].lower_bound({a,-1})->second > b){
auto p = s[i].insert({a,b}).first;
while(p != s[i].begin() && prev(p)->second >= b){
s[i].erase(prev(p));
}
if(p != prev(s[i].end()) && next(p)->first == p->first){
s[i].erase(next(p));
}
}
}
for(auto [a,b] : s[i]) pp[i].emplace_back(a,b);
}
vector<long long> bl[L][n-1]; vector<int> blt[L][n-1];
for(int l = 0;l < L;l++){
for(int i = 0;i < n-1;i++){
bl[l][i].resize(s[i].size());
blt[l][i].resize(s[i].size());
}
}
vector<int> nxt[n-1];
for(int i = 0;i < n-1;i++){
for(int j = 0;j < pp[i].size();j++){
bl[0][i][j] = pp[i][j].second-pp[i][j].first;
blt[0][i][j] = j;
if(i==n-2) continue;
if(pp[i+1].back().first < pp[i][j].second) nxt[i].push_back(0);
else nxt[i].push_back(lower_bound(pp[i+1].begin(), pp[i+1].end(), pair<int,int>{pp[i][j].second, -1})-pp[i+1].begin());
}
}
for(int l = 1;l < L;l++){
for(int i = 0;i+(1<<l) < n;i++){
for(int j = 0;j < pp[i].size();j++){
int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
int nb = pp[i+(1<<l-1)-1][blt[l-1][i][j]].second;
if(na < nb){
bl[l][i][j] = bl[l-1][i][j] + t+na-nb + bl[l-1][i+(1<<l-1)][0];
blt[l][i][j] = blt[l-1][i+(1<<l-1)][0];
} else {
bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
}
}
}
}
int q;cin >> q;
while(q--){
int l,r;cin >> l >> r;l--;r--;
long long aans = LONG_LONG_MAX;
for(int j = 0;j < pp[l].size();j++){
long long ans = pp[l][j].second-pp[l][j].first;
int k = j;l++;
for(int i = L-1;i >= 0;i--){
if(l+(1<<i) > r) continue;
int na = pp[l][nxt[l-1][k]].first;
int nb = pp[l-1][k].second;
if(na < nb){
ans += t+na-nb+bl[i][l][0];
k = blt[i][l][0];
} else {
ans += na-nb+bl[i][l][nxt[l-1][k]];
k = blt[i][l][nxt[l-1][k]];
}
l+=1<<i;
}
aans = min(aans, ans);
}
cout << aans << '\n';
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:33:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for(int j = 0;j < pp[i].size();j++){
| ~~^~~~~~~~~~~~~~
Main.cpp:43:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int j = 0;j < pp[i].size();j++){
| ~~^~~~~~~~~~~~~~
Main.cpp:44:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
44 | int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
| ~^~
Main.cpp:44:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
44 | int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
| ~^~
Main.cpp:45:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
45 | int nb = pp[i+(1<<l-1)-1][blt[l-1][i][j]].second;
| ~^~
Main.cpp:47:76: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
47 | bl[l][i][j] = bl[l-1][i][j] + t+na-nb + bl[l-1][i+(1<<l-1)][0];
| ~^~
Main.cpp:48:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
48 | blt[l][i][j] = blt[l-1][i+(1<<l-1)][0];
| ~^~
Main.cpp:50:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
50 | bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
| ~^~
Main.cpp:50:90: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
50 | bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
| ~^~
Main.cpp:51:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
51 | blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
| ~^~
Main.cpp:51:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
51 | blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
| ~^~
Main.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int j = 0;j < pp[l].size();j++){
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
600 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
348 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
