#include <stdio.h>
#include <stdlib.h>
#define N 300001
#define LIM 19
#define INF 1000000000000000LL
typedef long long ll;
typedef struct {
ll a, b, c, d;
int i;
} Query;
typedef struct {
ll cost, time;
} Pair;
ll l[N], r[N], t[N], ans[N], jump_min[N][LIM], jump_max[N][LIM], free_cit[N][3];
Pair ansl[N][LIM], ansr[N][LIM], ansm[N][LIM];
int n, q;
Pair trans(int i, int bt, int time) {
if (time <= l[i]) {
return ansl[i][bt];
}
return ansm[i][bt];
}
void binary_search(int i, int t, int *idx1, int *idx2) {
*idx1 = *idx2 = i;
ll max_val = l[i] - i, min_val = r[i] - i - 1;
for (int bt = LIM - 1; bt >= 0; --bt) {
if (*idx1 + (1 << bt) < n) {
ll m1 = max_val;
if (jump_max[*idx1 + 1][bt] > m1)
m1 = jump_max[*idx1 + 1][bt];
if (m1 <= t - i) {
max_val = m1;
*idx1 += 1 << bt;
}
}
if (*idx2 + (1 << bt) < n) {
ll m2 = min_val;
if (jump_min[*idx2 + 1][bt] < m2)
m2 = jump_min[*idx2 + 1][bt];
if (t - i <= m2) {
min_val = m2;
*idx2 += 1 << bt;
}
}
}
if (max_val <= t - i)
*idx1 = *idx1 + 1 < n ? *idx1 + 1 : n;
if (t - i <= min_val)
*idx2 = *idx2 + 1 < n ? *idx2 + 1 : n;
}
Pair __ans(int i, int x, ll t) {
ll ans = 0;
for (int bt = 0; bt < LIM; ++bt) {
if (x & (1 << bt)) {
Pair next;
if (t <= l[i]) {
next = ansl[i][bt];
} else if (t >= r[i] - 1) {
next = ansr[i][bt];
ans += t - r[i] + 1;
} else {
next = ansm[i][bt];
}
ans += next.cost;
t = next.time;
i += (1 << bt);
}
}
return (Pair){ans, t};
}
Pair _ans(int i, int x, ll t) {
int idx1, idx2;
binary_search(i, t, &idx1, &idx2);
ll free_jumps = (idx1 < idx2 ? idx1 : idx2) - i;
if (x <= free_jumps) {
ll del = t + x > r[i + x] - 1 ? t + x - (r[i + x] - 1) : 0;
Pair res = {del, t + x - del};
return res;
}
if (idx1 < idx2) {
return __ans(idx1, x - free_jumps, l[idx1]);
} else {
Pair p = __ans(idx2, x - free_jumps, r[idx2] - 1);
Pair res = {t + free_jumps - r[idx2] + p.cost + 1, p.time};
return res;
}
}
ll adjust(int i, int t) { return t - r[i + 1] + 2 > 0 ? t - r[i + 1] + 2 : 0; }
void solve(Query *queries, int qsize) {
for (int i = 0, time = l[0]; i < n; ++i) {
if (time < l[i]) {
time = l[i];
} else if (time > r[i] - 1) {
time = r[i] - 1;
}
t[i] = time;
time++;
}
for (int i = 0; i < n; ++i) {
ll v1 = adjust(i, l[i]);
ll v2 = adjust(i, r[i] - 1);
ll v3 = adjust(i, t[i]);
ansl[i][0] = (Pair){v1, l[i] - v1 + 1};
ansr[i][0] = (Pair){v2, r[i] - v2};
ansm[i][0] = (Pair){v3, t[i] - v3 + 1};
jump_max[i][0] = l[i] - i;
jump_min[i][0] = r[i] - i - 1;
}
for (int bt = 1; bt < LIM; ++bt) {
for (int i = 0; i < n; ++i) {
jump_min[i][bt] = jump_min[i][bt - 1];
jump_max[i][bt] = jump_max[i][bt - 1];
if (i + (1 << (bt - 1)) < n) {
if (jump_min[i + (1 << (bt - 1))][bt - 1] < jump_min[i][bt])
jump_min[i][bt] = jump_min[i + (1 << (bt - 1))][bt - 1];
if (jump_max[i + (1 << (bt - 1))][bt - 1] > jump_max[i][bt])
jump_max[i][bt] = jump_max[i + (1 << (bt - 1))][bt - 1];
}
}
}
for (int i = 0, idx1, idx2; i < n; ++i) {
binary_search(i, l[i], &idx1, &idx2);
free_cit[i][0] = (idx1 < idx2 ? idx1 : idx2) - i;
binary_search(i, r[i] - 1, &idx1, &idx2);
free_cit[i][1] = (idx1 < idx2 ? idx1 : idx2) - i;
binary_search(i, t[i], &idx1, &idx2);
free_cit[i][2] = (idx1 < idx2 ? idx1 : idx2) - i;
}
for (int bt = 1; bt < LIM; ++bt) {
for (int i = 0; i + (1 << (bt - 1)) < n; ++i) {
if ((1 << bt) <= free_cit[i][0]) {
ll time = l[i] + (1 << bt);
ll v = adjust(i + (1 << bt) - 1, time);
ansl[i][bt] = (Pair){v, time - v};
} else {
if (free_cit[i][0] <= (1 << (bt - 1))) {
Pair tmp1 = ansl[i][bt - 1];
Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
ansl[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
} else {
Pair tmp1 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].time);
ansl[i][bt] = (Pair){ansl[i][bt - 1].cost + tmp1.cost, tmp1.time};
}
}
if ((1 << bt) <= free_cit[i][1]) {
ll time = r[i] - 1 + (1 << bt);
ll v = adjust(i + (1 << bt) - 1, time);
ansr[i][bt] = (Pair){v, time - v};
} else {
if (free_cit[i][1] <= (1 << (bt - 1))) {
Pair tmp1 = ansr[i][bt - 1];
Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
ansr[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
} else {
Pair tmp2 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].time);
ansr[i][bt] = (Pair){ansr[i][bt - 1].cost + tmp2.cost, tmp2.time};
}
}
if ((1 << bt) <= free_cit[i][2]) {
ll time = t[i] + (1 << bt);
ll v = adjust(i + (1 << bt) - 1, time);
ansm[i][bt] = (Pair){v, time - v};
} else {
if (free_cit[i][2] <= (1 << (bt - 1))) {
Pair tmp1 = ansm[i][bt - 1];
Pair tmp2 = trans(i + (1 << (bt - 1)), bt - 1, tmp1.time);
ansm[i][bt] = (Pair){tmp1.cost + tmp2.cost, tmp2.time};
} else {
Pair tmp3 = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansm[i][bt - 1].time);
ansm[i][bt] = (Pair){ansm[i][bt - 1].cost + tmp3.cost, tmp3.time};
}
}
}
}
for (int k = 0; k < qsize; ++k) {
ll a = queries[k].a, b = queries[k].b, c = queries[k].c, d = queries[k].d;
int i = queries[k].i;
Pair res = _ans(a, c - a - 1, b);
ll cost = res.cost, time = res.time;
if (time < l[c - 1])
time = l[c - 1];
else if (time > r[c - 1] - 1) {
cost += time - r[c - 1] + 1;
time = r[c - 1] - 1;
}
if (++time > d)
cost += time - d;
if (cost > ans[i])
ans[i] = cost;
}
}
int main() {
scanf("%d %d", &n, &q);
l[n - 1] = INF;
r[n - 1] = INF + 1;
l[n] = r[n] = INF + 2;
for (int i = 0; i < n - 1; ++i) {
scanf("%lld %lld", &l[i], &r[i]);
}
Query *q1 = (Query *)malloc(q * sizeof(Query));
Query *q2 = (Query *)malloc(q * sizeof(Query));
int q1s = 0, q2s = 0;
for (int i = 0, a, b, c, d, t; i < q; ++i) {
scanf("%d %d %d %d %d", &t, &a, &b, &c, &d);
--a, --c;
if (a == c)
continue;
if (a < c) {
q1[q1s++] = (Query){a, b, c, d, i};
} else {
q2[q2s++] = (Query){n - a - 1, b, n - c - 1, d, i};
}
}
solve(q1, q1s);
for (int i = 0; i < n - 1 - i; ++i) {
ll tmp = l[i];
l[i] = l[n - 2 - i];
l[n - 2 - i] = tmp;
tmp = r[i];
r[i] = r[n - 2 - i];
r[n - 2 - i] = tmp;
}
solve(q2, q2s);
for (int i = 0; i < q; ++i) {
printf("%lld\n", ans[i]);
}
free(q1);
free(q2);
return 0;
}
Compilation message (stderr)
timeleap.c: In function 'main':
timeleap.c:206:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
206 | scanf("%d %d", &n, &q);
| ^~~~~~~~~~~~~~~~~~~~~~
timeleap.c:211:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | scanf("%lld %lld", &l[i], &r[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.c:217:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
217 | scanf("%d %d %d %d %d", &t, &a, &b, &c, &d);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |