#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
int main() {
ios_base::sync_with_stdio(0); cin.tie(NULL);
int n, t;
cin >> n >> t;
// fi -> (city, next flight idx)
// se -> (time of arrival, time elapsed)
// each city has different number of flights
vector<pair<pair<int, int>, pair<int, ll>>> nxt[18][n + 1];
vector<pair<int, int>> flights[n + 1];
for (int i = 1; i < n; ++i) {
int m;
cin >> m;
vector<pair<int, int>> a;
for (int i = 1; i <= m; ++i) {
int x, y;
cin >> x >> y;
a.pb(mp(x, y));
}
sort(a.begin(), a.end());
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
vector<pair<int, int>> res;
for (auto [l, r] : a) {
while (pq.size() && pq.top().fi < l) {
res.push_back(mp(pq.top().se, pq.top().fi));
pq.pop();
}
while (pq.size() && pq.top().fi >= r) {
pq.pop();
}
pq.push({r, l});
}
while (pq.size()) {
res.push_back(mp(pq.top().se, pq.top().fi));
pq.pop();
}
flights[i] = res;
}
for(int i = n - 1; i >= 1; --i) {
for (int j = 0; j < 18; ++j) {
nxt[j][i].resize(flights[i].size() + 1);
}
for (int j = 0; j < 18; ++j) {
for (int k = 0; k < flights[i].size(); ++k) {
if (j == 0) {
nxt[j][i][k] = mp(mp(i + 1, lb(flights[i + 1].begin(), flights[i + 1].end(), mp(flights[i][k].se, 0)) - flights[i + 1].begin()), mp(flights[i][k].se, flights[i][k].se - flights[i][k].fi));
// cerr << "DEB2 " << i << " " << k << " " << nxt[j][i][k].fi.fi << " " << nxt[j][i][k].fi.se << " " << nxt[j][i][k].se.fi << " " << nxt[j][i][k].se.se << endl;
} else {
auto [city, idx] = nxt[j - 1][i][k].fi;
auto [toa, elapsed] = nxt[j - 1][i][k].se;
if (city == n || city == 0) {
// cerr << "NXT " << j << " " << i << " " << k << " " << city << endl;
continue;
}
if (idx == flights[city].size()) {
elapsed += t - toa + flights[city][0].fi;
idx = 0;
} else {
elapsed += flights[city][idx].fi - toa;
}
nxt[j][i][k] = mp(nxt[j - 1][city][idx].fi, mp(nxt[j - 1][city][idx].se.fi, elapsed + nxt[j - 1][city][idx].se.se));
// cerr << "DEB3 " << j << " " << i << " " << k << " " << nxt[j - 1][city][idx].fi.fi << " " << nxt[j - 1][city][idx].fi.se << endl;
}
}
}
}
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
// binlift from l to r
ll ans = 0;
for (int init = 0; init < flights[l].size(); ++init) {
ll res = 0;
int pos = l, idx = init;
for (int i = 17; i >= 0; --i) {
if (nxt[i][pos][idx].fi.fi > 0 && nxt[i][pos][idx].fi.fi < r) {
// cerr << "HERE" << endl;
// cerr << i << " " << pos << " " << idx << " " << nxt[i][pos].size() << endl;
res += nxt[i][pos][idx].se.se;
pair<pair<int, int>, pair<int, int>> tmp = nxt[i][pos][idx];
pos = tmp.fi.fi;
idx = tmp.fi.se;
auto [toa, elapsed] = tmp.se;
// cerr << toa << " " << elapsed << endl;
// cerr << "GOT VALUE" << endl;
if (idx == flights[pos].size()) {
// cerr << "HERE" << endl;
// cerr << pos << " " << flights[pos].size() << endl;
res += t - toa + flights[pos][0].fi;
idx = 0;
} else {
res += flights[pos][idx].fi - toa;
}
}
}
// cerr << "NEW VALUE: " << 0 << " " << pos << " " << idx << endl;
ans = max(ans, res + nxt[0][pos][idx].se.se);
break;
}
cout << ans << endl;
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |