This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
struct segTree{
int minV[400002], minIdx[400002];
void init(int i, int l, int r, int *A){
if(l==r){
minV[i] = A[l], minIdx[i] = l;
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
if(minV[i*2] <= minV[i*2+1]) minV[i] = minV[i*2], minIdx[i] = minIdx[i*2];
else minV[i] = minV[i*2+1], minIdx[i] = minIdx[i*2+1];
}
pair<int, int> query(int i, int l, int r, int s, int e){
if(r<s || e<l) return make_pair(INT_MAX, -1);
if(s<=l && r<=e) return make_pair(minV[i], minIdx[i]);
int m = (l+r)>>1;
return min(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
struct dat{
ll x, y;
dat(){}
dat(ll x, ll y): x(x), y(y){}
bool operator<(const dat &r)const{
if(x != r.x) return x < r.x;
return y > r.y;
}
bool operator<(const ll &r)const{
return x < r;
}
};
struct Query{
int l, r, idx;
Query(){}
Query(int l, int r, int idx): l(l), r(r), idx(idx){}
};
int n, q, K; ll T;
dat arr[100002], arrRev[100002];
int S[100002], E[100002], sz[100002];
int nxtR[100002], dayR[100002], nxtL[100002], dayL[100002];
int nxtRsps[100002][20], dayRsps[100002][20], nxtLsps[100002][20], dayLsps[100002][20];
int recentL[100002], Lloc[100002], recentR[100002], Rloc[100002];
int qlx[500002], qld[500002], qrx[500002], qrd[500002], qlcnt, qrcnt;
vector<Query> queries[100002];
ll ans[300002];
int main(){
scanf("%d %lld", &n, &T);
for(int i=1; i<n; i++){
int s;
scanf("%d", &s);
vector<dat> vec;
vec.resize(s);
for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);
sort(vec.begin(), vec.end());
vector<dat> vec2;
for(int j=0; j<s; j++){
while(!vec2.empty() && vec2.back().y >= vec[j].y) vec2.pop_back();
vec2.push_back(vec[j]);
}
sz[i] = (int)vec2.size();
S[i] = E[i-1] + 1, E[i] = S[i] + sz[i] - 1;
for(int j=0; j<sz[i]; j++) arr[S[i]+j] = vec2[j];
for(int j=S[i]; j<=E[i]; j++) arrRev[j] = dat(arr[j].y, arr[j].x);
}
tree.init(1, 1, n-1, sz);
for(int d=1; d<=n-2; d++){
for(int i=S[d]; i<=E[d]; i++){
int L = S[d+1], R = E[d+1];
if(arr[R].x >= arr[i].y) nxtR[i] = lower_bound(arr+L, arr+R+1, dat(arr[i].y, INF)) - arr;
else nxtR[i] = L, dayR[i] = 1;
}
}
for(int d=3; d<=n; d++){
for(int i=S[d-1]; i<=E[d-1]; i++){
int L = S[d-2], R = E[d-2];
if(arrRev[L].x <= arrRev[i].y) nxtL[i] = upper_bound(arrRev+L, arrRev+R+1, dat(arrRev[i].y, -INF)) - arrRev - 1;
else nxtL[i] = R, dayL[i] = 1;
}
}
K = E[n-1];
for(int i=1; i<=K; i++) nxtLsps[i][0] = nxtL[i], nxtRsps[i][0] = nxtR[i], dayLsps[i][0] = dayL[i], dayRsps[i][0] = dayR[i];
for(int d=1; d<20; d++){
for(int i=1; i<=K; i++){
nxtLsps[i][d] = nxtLsps[nxtLsps[i][d-1]][d-1];
dayLsps[i][d] = dayLsps[i][d-1] + dayLsps[nxtLsps[i][d-1]][d-1];
nxtRsps[i][d] = nxtRsps[nxtRsps[i][d-1]][d-1];
dayRsps[i][d] = dayRsps[i][d-1] + dayRsps[nxtRsps[i][d-1]][d-1];
}
}
scanf("%d", &q);
for(int i=1; i<=q; i++){
int l, r;
scanf("%d %d", &l, &r);
int minIdx = tree.query(1, 1, n-1, l, r-1).second;
queries[minIdx].push_back(Query(l, r, i));
}
for(int m=1; m<n; m++){
qlcnt = qrcnt = 0;
for(Query &p: queries[m]){
int L = p.l, R = p.r, LD = m - L, RD = R - m - 1;
if(recentL[L] != m){
recentL[L] = m, Lloc[L] = qlcnt+1;
for(int i=S[m]; i<=E[m]; i++){
int x = ++qlcnt;
qlx[x] = i, qld[x] = 0;
for(int d=0; d<20; d++) if((LD>>d)&1) qld[x] += dayLsps[qlx[x]][d], qlx[x] = nxtLsps[qlx[x]][d];
}
}
if(recentR[R] != m){
recentR[R] = m, Rloc[R] = qrcnt+1;
for(int i=S[m]; i<=E[m]; i++){
int x = ++qrcnt;
qrx[x] = i, qrd[x] = 0;
for(int d=0; d<20; d++) if((RD>>d)&1) qrd[x] += dayRsps[qrx[x]][d], qrx[x] = nxtRsps[qrx[x]][d];
}
}
int idx = p.idx;
ans[idx] = LLONG_MAX;
for(int i=S[m]; i<=E[m]; i++){
int lp = Lloc[L] + (i - S[m]), rp = Rloc[R] + (i - S[m]);
ll v = (qld[lp] + qrd[rp]) * T + (arr[qrx[rp]].y - arrRev[qlx[lp]].y);
ans[idx] = min(ans[idx], v);
}
}
}
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d %lld", &n, &T);
| ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d", &s);
| ~~~~~^~~~~~~~~~
Main.cpp:71:37: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
71 | for(int j=0; j<s; j++) scanf("%lld %lld", &vec[j].x, &vec[j].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
Main.cpp:117:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | scanf("%d %d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~~
# | 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... |