#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MAXN 300010
#ifdef DEBUG
#define D(x...) printf(x)
#else
#define D(x...)
#endif
int n, q;
int l[MAXN], r[MAXN];
int l1[MAXN], r1[MAXN], cost[MAXN][2][20], sta[MAXN];
pair<int, int> jump[MAXN][2][20];
vector<int> startsat[MAXN];
pair<int, int> firstjump[MAXN];
int A[MAXN], T1[MAXN], B[MAXN], T2[MAXN], swapped[300010];
void makejump()
{
int sz = 1;
sta[0] = n;
l1[n] = 1e15;
for (int i = n-1; i >= 1; i--)
{
while (sz && l1[sta[sz-1]] <= l1[i]) sz--;
// from l1
jump[i][0][0] = { sta[sz-1], 0 };
cost[i][0][0] = 0;
// from r1
int s = 0;
int e = sz-1;
while (s != e)
{
int m = (s+e+1)/2;
if (r1[i] >= l1[sta[m]]) e = m-1;
else s = m;
}
jump[i][1][0] = { sta[s], 0 };
cost[i][1][0] = 0;
sta[sz++] = i;
for (auto a : startsat[i])
{
int s = 0;
int e = sz-1;
while (s != e)
{
int m = (s+e+1)/2;
if (T1[a]-A[a] >= l1[sta[m]]) e = m-1;
else s = m;
}
firstjump[a] = { sta[s], 0 };
}
}
sta[0] = n;
sz = 1;
r1[n] = -1e15;
for (int i = n-1; i >= 1; i--)
{
while (sz && r1[sta[sz-1]] >= r1[i]) sz--;
// from r1
if (jump[i][1][0].first > sta[sz-1])
{
jump[i][1][0] = { sta[sz-1], 1 };
cost[i][1][0] = r1[i] - r1[sta[sz-1]];
}
// from l1
int s = 0;
int e = sz-1;
while (s != e)
{
int m = (s+e+1)/2;
if (l1[i] <= r1[sta[m]]) e = m-1;
else s = m;
}
if (jump[i][0][0].first > sta[s])
{
jump[i][0][0] = { sta[s], 1 };
cost[i][0][0] = l1[i] - r1[sta[s]];
}
sta[sz++] = i;
for (auto a : startsat[i])
{
int s = 0;
int e = sz-1;
while (s != e)
{
int m = (s+e+1)/2;
if (T1[a]-A[a] <= r1[sta[m]]) e = m-1;
else s = m;
}
firstjump[a] = min(firstjump[a], { sta[s], 1 } );
}
}
jump[n][0][0].first = jump[n][1][0].first = n;
for (int k = 1; k < 20; k++)
{
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < 2; j++)
{
jump[i][j][k] = jump[jump[i][j][k-1].first][jump[i][j][k-1].second][k-1];
cost[i][j][k] = cost[i][j][k-1] + cost[jump[i][j][k-1].first][jump[i][j][k-1].second][k-1];
}
}
}
}
int anss[300010];
#undef int
int main()
{
#define int long long
scanf("%lld%lld", &n, &q);
for (int i = 1; i < n; i++)
{
scanf("%lld%lld", &l[i], &r[i]);
r[i]--;
}
for (int i = 1; i < n; i++)
{
l1[i] = l[i]-i;
r1[i] = r[i]-i;
}
for (int i = 0; i < q; i++)
{
int t;
scanf("%lld%lld%lld%lld%lld", &t, &A[i], &T1[i], &B[i], &T2[i]);
if (A[i] < B[i]) startsat[A[i]].push_back(i);
}
makejump();
for (int f = 0; f < q; f++)
{
int a, t1, b, t2;
a = A[f], t1 = T1[f], b = B[f], t2 = T2[f];
if (a == b)
{
if (t1 <= t2) anss[f] = 0;
else anss[f] = t1-t2;
}
else if (a < b)
{
int ans = 0;
int i = a;
int jumped = 0;
int j = 0;
t2-=b;
// do the first jump
if (firstjump[f].first < b)
{
jumped = 1;
i = firstjump[f].first;
j = firstjump[f].second;
D("jumping to %lld %lld t1 r1 %lld %lld from %lld\n", i, j, t1, r1[i], a);
ans += max(0ll, t1-a-r1[i]);
D("%lld\n", ans);
}
if (jumped)
{
for (int k = 19; k >= 0; k--)
{
if (jump[i][j][k].first < b)
{
D("jumping again to %lld %lld cost %lld k %lld\n", jump[i][j][k].first, jump[i][j][k].second, cost[i][j][k], k);
ans += cost[i][j][k];
tie(i, j) = jump[i][j][k];
}
}
}
if (jumped)
{
if (j) t1 = r1[i];
else t1 = l1[i];
}
else t1-=a;
ans += max(0ll, t1-t2);
anss[f] = ans;
}
}
for (int i = 1; i < n; i++)
{
l1[i] = l[n-i]-i;
r1[i] = r[n-i]-i;
startsat[i].clear();
}
for (int i = 0; i < q; i++)
{
if (A[i] > B[i])
{
swapped[i] = 1;
A[i] = n-A[i]+1;
B[i] = n-B[i]+1;
startsat[A[i]].push_back(i);
}
}
makejump();
for (int f = 0; f < q; f++)
{
int a, t1, b, t2;
a = A[f], t1 = T1[f], b = B[f], t2 = T2[f];
if (swapped[f])
{
int ans = 0;
int i = a;
int jumped = 0;
int j = 0;
t2-=b;
// do the first jump
if (firstjump[f].first < b)
{
jumped = 1;
i = firstjump[f].first;
j = firstjump[f].second;
D("jumping to %lld %lld t1 r1 %lld %lld from %lld\n", i, j, t1, r1[i], a);
ans += max(0ll, t1-a-r1[i]);
D("%lld\n", ans);
}
if (jumped)
{
for (int k = 19; k >= 0; k--)
{
if (jump[i][j][k].first < b)
{
D("jumping again to %lld %lld cost %lld k %lld\n", jump[i][j][k].first, jump[i][j][k].second, cost[i][j][k], k);
ans += cost[i][j][k];
tie(i, j) = jump[i][j][k];
}
}
}
if (jumped)
{
if (j) t1 = r1[i];
else t1 = l1[i];
}
else t1-=a;
ans += max(0ll, t1-t2);
anss[f] = ans;
}
}
for (int i = 0; i < q; i++)
{
printf("%lld\n", anss[i]);
}
}
Compilation message
timeleap.cpp: In function 'int main()':
timeleap.cpp:111:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~
timeleap.cpp:114:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld", &l[i], &r[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.cpp:125:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld%lld%lld%lld%lld", &t, &A[i], &T1[i], &B[i], &T2[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2547 ms |
311872 KB |
Output is correct |
| 2 |
Correct |
2070 ms |
301480 KB |
Output is correct |
| 3 |
Correct |
2078 ms |
304936 KB |
Output is correct |
| 4 |
Correct |
2062 ms |
296144 KB |
Output is correct |
| 5 |
Correct |
2349 ms |
317016 KB |
Output is correct |
| 6 |
Correct |
2149 ms |
311804 KB |
Output is correct |
| 7 |
Correct |
2567 ms |
321072 KB |
Output is correct |
| 8 |
Correct |
2678 ms |
333560 KB |
Output is correct |
| 9 |
Correct |
2260 ms |
298336 KB |
Output is correct |
| 10 |
Correct |
2492 ms |
319868 KB |
Output is correct |
| 11 |
Correct |
2310 ms |
317296 KB |
Output is correct |
| 12 |
Correct |
2435 ms |
338540 KB |
Output is correct |
| 13 |
Correct |
2557 ms |
343336 KB |
Output is correct |
| 14 |
Correct |
10 ms |
7424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
23 ms |
14840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
