#include "bits/stdc++.h" /** keep-include */
using namespace std;
#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
auto &operator<<(auto &o, pair<auto, auto> p) {
return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif
const int K=19, N=3e5+5;
vector<pii> loty[N];
vector<int> id[N];
vi best[K][N];
int nxt[K][N];
ll czas[K][N];
pair<int, ll> jump(int v, int t){
ll res=0;
for(int k=K-1; k>=0; k--){
if(t>=(1<<k)){
res+=czas[k][v];
v=nxt[k][v];
t-=(1<<k);
}
}
return mp(v, res);
}
void solve() {
int n, t;
cin>>n>>t;
vector<pair<pii, int> > co;
co.pb(mp(mp(0, 0), 0));
for(int i=1; i<n; i++){
int k;
cin>>k;
vector<pair<int, int> > V(k);
for(auto &j:V){
cin>>j.st>>j.nd;
}
sort(all(V));
vector<pii> V2;
for(auto &j:V){
while(V2.size() && V2.back().nd>=j.nd){
V2.pop_back();
}
V2.pb(j);
}
k=V2.size();
for(int j=0; j<k; j++){
id[i].pb(co.size());
co.pb(mp(V2[j], i));
}
loty[i]=V2;
}
for(int j=1; j<co.size(); j++){
auto &[seg, i] = co[j];
if(i!=n-1){
auto it=lower_bound(all(loty[i+1]), mp(seg.nd, 0));
if(it==loty[i+1].end()){
it=loty[i+1].begin();
nxt[0][j]=id[i+1][it-loty[i+1].begin()];
czas[0][j]=it->nd-seg.nd+t;
deb(czas[0][j], it->nd, seg.nd,t);
}
else{
nxt[0][j]=id[i+1][it-loty[i+1].begin()];
czas[0][j]=it->nd-seg.nd;
}
}
deb(j, seg, i, co[nxt[0][j]], czas[0][j]);
}
for(int k=1; k<K; k++){
for(int i=1; i<co.size(); i++){
nxt[k][i]=nxt[k-1][nxt[k-1][i]];
czas[k][i]=czas[k-1][i]+czas[k-1][nxt[k-1][i]];
}
}
for(int k=0; k<K; k++){
for(int i=1; i<n; i++){
vector<pair<int, pair<ll, int> > > V;//dokad, czas, id
for(int j=0; j<loty[i].size(); j++){
V.pb(mp(nxt[k][id[i][j]], mp(czas[k][id[i][j]]+loty[i][j].nd-loty[i][j].st, j)));
}
sort(all(V));
for(int j=0; j<V.size(); j++){
if(j==0 || V[j].st!=V[j-1].st){
best[k][i].pb(V[j].nd.nd);
}
}
assert(best[k][i].size());
}
}
map<pair<int, int> , ll> old_ans;
int q;
cin>>q;
while(q--){
int l, r;
cin>>l>>r;
if(old_ans.find(mp(l, r))!=old_ans.end()){
cout<<old_ans[mp(l, r)]<<"\n";
continue;
}
ll ans=1e18;
int k=0;
int dl=r-l-1;
while((1<<k)<=dl)k++;
k--;
//for(int i=0; i<loty[l].size(); i++){
for(int i:best[k][l]){
ll part=loty[l][i].nd-loty[l][i].st;
int lot=id[l][i];
deb(lot);
/*for(int j=l+1; j<r; j++){
part+=czas[0][lot];
lot=nxt[0][lot];
}*/
part+=jump(lot, dl).nd;
//deb(part);
ans=min(ans, part);
}
old_ans[mp(l, r)]=ans;
cout<<ans<<"\n";
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int tt = 1;
// cin >> tt;
FOR(te, 0, tt) solve();
return 0;
}
Compilation message
Main.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
17 | auto &operator<<(auto &o, pair<auto, auto> p) {
| ^~~~
Main.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
| ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | for(int j=1; j<co.size(); j++){
| ~^~~~~~~~~~
Main.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int i=1; i<co.size(); i++){
| ~^~~~~~~~~~
Main.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for(int j=0; j<loty[i].size(); j++){
| ~^~~~~~~~~~~~~~~
Main.cpp:107:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
107 | for(int j=0; j<V.size(); j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
148816 KB |
Output is correct |
| 2 |
Incorrect |
147 ms |
155868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
148816 KB |
Output is correct |
| 2 |
Incorrect |
147 ms |
155868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
148816 KB |
Output is correct |
| 2 |
Incorrect |
147 ms |
155868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
148816 KB |
Output is correct |
| 2 |
Incorrect |
147 ms |
155868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
148560 KB |
Output is correct |
| 2 |
Correct |
61 ms |
148548 KB |
Output is correct |
| 3 |
Incorrect |
468 ms |
181632 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
65 ms |
148816 KB |
Output is correct |
| 2 |
Incorrect |
147 ms |
155868 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
