#include <stdio.h>
#define N 300000
#define N_ (1 << 19) /* N_ = pow2(ceil(log2(N - 1))) */
#define INF 0x3f3f3f3f3f3f3f3fLL
long long abs_(long long a) { return a > 0 ? a : -a; }
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
long long aa1[N_], bb1[N_], cc1[N_], dd1[N_], aa2[N_], bb2[N_], cc2[N_], dd2[N_]; int n_;
void combine(long long a1, long long b1, long long c1, long long d1, long long a2, long long b2, long long c2, long long d2, long long *a3_, long long *b3_, long long *c3_, long long *d3_) {
long long a3, b3, c3, d3;
if (c1 > 0) {
a3 = a1, b3 = b1;
if (d1 < a2)
c3 = c1 + c2 + a2 - d1, d3 = c2 > 0 ? d2 : a2;
else if (d1 > b2)
c3 = c1 + c2 + d1 - b2, d3 = c2 > 0 ? d2 : b2;
else
c3 = c1 + c2, d3 = c2 > 0 ? d2 : d1;
} else {
if (b1 < a2)
a3 = b1, b3 = b1, c3 = c2 + a2 - b1, d3 = c2 > 0 ? d2 : a2;
else if (a1 > b2)
a3 = a1, b3 = a1, c3 = c2 + a1 - b2, d3 = c2 > 0 ? d2 : b2;
else
a3 = max(a1, a2), b3 = min(b1, b2), c3 = c2, d3 = d2;
}
*a3_ = a3, *b3_ = b3, *c3_ = c3, *d3_ = d3;
}
void pul(int i) {
int l = i << 1, r = l | 1;
combine(aa1[l], bb1[l], cc1[l], dd1[l], aa1[r], bb1[r], cc1[r], dd1[r], &aa1[i], &bb1[i], &cc1[i], &dd1[i]);
combine(aa2[r], bb2[r], cc2[r], dd2[r], aa2[l], bb2[l], cc2[l], dd2[l], &aa2[i], &bb2[i], &cc2[i], &dd2[i]);
}
void build(int *ll, int *rr, int n) {
int i;
n_ = 1;
while (n_ < n)
n_ <<= 1;
for (i = 0; i < n_; i++)
if (i < n) {
aa1[n_ + i] = ll[i] - i, bb1[n_ + i] = rr[i] - i, cc1[n_ + i] = 0, dd1[n_ + i] = 0;
aa2[n_ + i] = ll[i] + i, bb2[n_ + i] = rr[i] + i, cc2[n_ + i] = 0, dd2[n_ + i] = 0;
} else {
aa1[n_ + i] = 0, bb1[n_ + i] = 0, cc1[n_ + i] = 0, dd1[n_ + i] = 0;
aa2[n_ + i] = 0, bb2[n_ + i] = 0, cc2[n_ + i] = 0, dd2[n_ + i] = 0;
}
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void update(int i, long long a, long long b) {
int i_ = n_ + i;
aa1[i_] = a - i, bb1[i_] = b - i, cc1[i_] = 0, dd1[i_] = 0, aa2[i_] = a + i, bb2[i_] = b + i, cc2[i_] = 0, dd2[i_] = 0;
i = i_;
while (i > 1)
pul(i >>= 1);
}
void query1(int l, int r, long long *a, long long *b, long long *c, long long *d) {
long long al = -INF, bl = INF, cl = 0, dl = 0, ar = -INF, br = INF, cr = 0, dr = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
combine(al, bl, cl, dl, aa1[l], bb1[l], cc1[l], dd1[l], &al, &bl, &cl, &dl), l++;
if ((r & 1) == 0)
combine(aa1[r], bb1[r], cc1[r], dd1[r], ar, br, cr, dr, &ar, &br, &cr, &dr), r--;
}
combine(al, bl, cl, dl, ar, br, cr, dr, a, b, c, d);
}
void query2(int l, int r, long long *a, long long *b, long long *c, long long *d) {
long long al = -INF, bl = INF, cl = 0, dl = 0, ar = -INF, br = INF, cr = 0, dr = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
combine(aa2[l], bb2[l], cc2[l], dd2[l], al, bl, cl, dl, &al, &bl, &cl, &dl), l++;
if ((r & 1) == 0)
combine(ar, br, cr, dr, aa2[r], bb2[r], cc2[r], dd2[r], &ar, &br, &cr, &dr), r--;
}
combine(ar, br, cr, dr, al, bl, cl, dl, a, b, c, d);
}
int main() {
static int ll[N], rr[N];
int n, q, i, j;
scanf("%d%d", &n, &q), n--;
for (i = 0; i < n; i++)
scanf("%d%d", &ll[i], &rr[i]), rr[i]--;
build(ll, rr, n);
while (q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int l, r;
scanf("%d%d%d", &i, &l, &r), i--, r--;
update(i, l, r);
} else {
long long a, b, c, d;
int s, t;
scanf("%d%d%d%d", &i, &s, &j, &t), i--, j--;
if (i == j)
printf("%lld\n", max(s - t, 0));
else if (i < j) {
s -= i, t -= j;
query1(i, j - 1, &a, &b, &c, &d);
combine(s, s, 0, 0, a, b, c, d, &a, &b, &c, &d);
combine(a, b, c, d, t, t, 0, 0, &a, &b, &c, &d);
printf("%lld\n", (c + s - t) / 2);
} else {
s += i - 1, t += j - 1;
query2(j, i - 1, &a, &b, &c, &d);
combine(s, s, 0, 0, a, b, c, d, &a, &b, &c, &d);
combine(a, b, c, d, t, t, 0, 0, &a, &b, &c, &d);
printf("%lld\n", (c + s - t) / 2);
}
}
}
return 0;
}
Compilation message
timeleap.c: In function 'main':
timeleap.c:97:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d%d", &n, &q), n--;
| ^~~~~~~~~~~~~~~~~~~~~
timeleap.c:99:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%d%d", &ll[i], &rr[i]), rr[i]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.c:104:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | scanf("%d", &type);
| ^~~~~~~~~~~~~~~~~~
timeleap.c:108:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
108 | scanf("%d%d%d", &i, &l, &r), i--, r--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
timeleap.c:114:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d%d%d%d", &i, &s, &j, &t), i--, j--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
292 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
2 ms |
472 KB |
Output is correct |
| 13 |
Correct |
2 ms |
436 KB |
Output is correct |
| 14 |
Correct |
2 ms |
468 KB |
Output is correct |
| 15 |
Correct |
2 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
468 KB |
Output is correct |
| 17 |
Correct |
1 ms |
436 KB |
Output is correct |
| 18 |
Correct |
2 ms |
432 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
428 KB |
Output is correct |
| 21 |
Correct |
1 ms |
468 KB |
Output is correct |
| 22 |
Correct |
2 ms |
468 KB |
Output is correct |
| 23 |
Correct |
1 ms |
432 KB |
Output is correct |
| 24 |
Correct |
2 ms |
468 KB |
Output is correct |
| 25 |
Correct |
2 ms |
468 KB |
Output is correct |
| 26 |
Correct |
2 ms |
468 KB |
Output is correct |
| 27 |
Correct |
2 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
480 KB |
Output is correct |
| 29 |
Correct |
1 ms |
468 KB |
Output is correct |
| 30 |
Correct |
1 ms |
432 KB |
Output is correct |
| 31 |
Correct |
1 ms |
428 KB |
Output is correct |
| 32 |
Correct |
1 ms |
432 KB |
Output is correct |
| 33 |
Correct |
1 ms |
428 KB |
Output is correct |
| 34 |
Correct |
2 ms |
432 KB |
Output is correct |
| 35 |
Correct |
1 ms |
468 KB |
Output is correct |
| 36 |
Correct |
2 ms |
468 KB |
Output is correct |
| 37 |
Correct |
2 ms |
440 KB |
Output is correct |
| 38 |
Correct |
1 ms |
468 KB |
Output is correct |
| 39 |
Correct |
2 ms |
520 KB |
Output is correct |
| 40 |
Correct |
2 ms |
468 KB |
Output is correct |
| 41 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
88 ms |
44088 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
0 ms |
340 KB |
Output is correct |
| 5 |
Correct |
0 ms |
340 KB |
Output is correct |
| 6 |
Correct |
0 ms |
340 KB |
Output is correct |
| 7 |
Correct |
0 ms |
340 KB |
Output is correct |
| 8 |
Correct |
0 ms |
292 KB |
Output is correct |
| 9 |
Correct |
0 ms |
340 KB |
Output is correct |
| 10 |
Correct |
0 ms |
340 KB |
Output is correct |
| 11 |
Correct |
2 ms |
468 KB |
Output is correct |
| 12 |
Correct |
2 ms |
472 KB |
Output is correct |
| 13 |
Correct |
2 ms |
436 KB |
Output is correct |
| 14 |
Correct |
2 ms |
468 KB |
Output is correct |
| 15 |
Correct |
2 ms |
468 KB |
Output is correct |
| 16 |
Correct |
1 ms |
468 KB |
Output is correct |
| 17 |
Correct |
1 ms |
436 KB |
Output is correct |
| 18 |
Correct |
2 ms |
432 KB |
Output is correct |
| 19 |
Correct |
1 ms |
468 KB |
Output is correct |
| 20 |
Correct |
1 ms |
428 KB |
Output is correct |
| 21 |
Correct |
1 ms |
468 KB |
Output is correct |
| 22 |
Correct |
2 ms |
468 KB |
Output is correct |
| 23 |
Correct |
1 ms |
432 KB |
Output is correct |
| 24 |
Correct |
2 ms |
468 KB |
Output is correct |
| 25 |
Correct |
2 ms |
468 KB |
Output is correct |
| 26 |
Correct |
2 ms |
468 KB |
Output is correct |
| 27 |
Correct |
2 ms |
468 KB |
Output is correct |
| 28 |
Correct |
1 ms |
480 KB |
Output is correct |
| 29 |
Correct |
1 ms |
468 KB |
Output is correct |
| 30 |
Correct |
1 ms |
432 KB |
Output is correct |
| 31 |
Correct |
1 ms |
428 KB |
Output is correct |
| 32 |
Correct |
1 ms |
432 KB |
Output is correct |
| 33 |
Correct |
1 ms |
428 KB |
Output is correct |
| 34 |
Correct |
2 ms |
432 KB |
Output is correct |
| 35 |
Correct |
1 ms |
468 KB |
Output is correct |
| 36 |
Correct |
2 ms |
468 KB |
Output is correct |
| 37 |
Correct |
2 ms |
440 KB |
Output is correct |
| 38 |
Correct |
1 ms |
468 KB |
Output is correct |
| 39 |
Correct |
2 ms |
520 KB |
Output is correct |
| 40 |
Correct |
2 ms |
468 KB |
Output is correct |
| 41 |
Correct |
1 ms |
340 KB |
Output is correct |
| 42 |
Runtime error |
88 ms |
44088 KB |
Execution killed with signal 11 |
| 43 |
Halted |
0 ms |
0 KB |
- |
