Submission #674034

#	Time	Username	Problem	Language	Result	Execution time	Memory
674034		rainboy	Bitaro, who Leaps through Time (JOI19_timeleap)	C11	100 / 100	555 ms	88612 KiB

timeleap

#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_ * 2], bb1[N_ * 2], cc1[N_ * 2], dd1[N_ * 2], aa2[N_ * 2], bb2[N_ * 2], cc2[N_ * 2], dd2[N_ * 2]; 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 (stderr)

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--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 30 / 30
• Subtask 3: 66 / 66