oj.uz

답안 #674033

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
674033 2022-12-22T16:35:10 Z rainboy Bitaro, who Leaps through Time (JOI19_timeleap) C
4 / 100
 88 ms 44088 KB 
#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--;
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 88 ms 44088 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 66.0

# 결과 실행 시간 메모리 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 -