oj.uz

Submission #644994

# Submission time Handle Problem Language Result Execution time Memory
644994 2022-09-25T18:45:46 Z rainboy Ants and Sugar (JOI22_sugar) C
100 / 100
 1612 ms 79284 KB 
#include <stdio.h>
 
#define N	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N + 1))) */
 
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; }
 
unsigned int X = 12345;
 
int rand_() {
	return (X *= 3) >> 1;
}
 
int tt[N], xx[N], yy[N], n, n_; long long kk[N];
 
int *ww, mode;
 
void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
 
		while (j < k) {
			int c = ww[ii[j]] != ww[i_] ? ww[ii[j]] - ww[i_] : (mode == 0 ? tt[ii[j]] - tt[i_] : tt[i_] - tt[ii[j]]);
 
			if (c == 0)
				j++;
			else if (c < 0) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		}
		sort(ii, l, i);
		l = k;
	}
}
 
void pul1(long long *st, int i) {
	st[i] = st[i << 1 | 0] + st[i << 1 | 1];
}
 
void update1(long long *st, int i, long long x) {
	i += n_;
	st[i] += x;
	while (i > 1)
		pul1(st, i >>= 1);
}
 
int query1l(long long *st, int l) {
	int r = n_ - 1, i;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l]) {
				i = l;
				while (i < n_)
					i = st[i << 1 | 0] ? i << 1 | 0 : i << 1 | 1;
				return i - n_;
			}
			l++;
		}
	return -1;
}
 
int query1r(long long *st, int r) {
	int l = 0, i;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st[r]) {
				i = r;
				while (i < n_)
					i = st[i << 1 | 1] ? i << 1 | 1 : i << 1 | 0;
				return i - n_;
			}
			r--;
		}
	return -1;
}
 
void pul2(long long *ss, long long *pp, int i) {
	int l = i << 1, r = l | 1;
 
	ss[i] = ss[l] + ss[r];
	pp[i] = min(pp[l], ss[l] + pp[r]);
}
 
void update2(long long *ss, long long *pp, int i, long long x) {
	i += n_;
	ss[i] += x, pp[i] = min(ss[i], 0);
	while (i > 1)
		pul2(ss, pp, i >>= 1);
}
 
long long query2s(long long *ss, int l, int r) {
	long long sum = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			sum += ss[l++];
		if ((r & 1) == 0)
			sum += ss[r--];
	}
	return sum;
}
 
long long query2p(long long *ss, long long *pp, int l, int r) {
	long long s = query2s(ss, 0, l - 1), sl = 0, pl = 0, pr = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			pl = min(pl, sl + pp[l]), sl += ss[l], l++;
		if ((r & 1) == 0)
			pr = min(pp[r], ss[r] + pr), r--;
	}
	return s + min(pl, sl + pr);
}
 
int main() {
	static int ii[N], jj[N];
	static long long st1[N_ * 2], st2[N_ * 2], ss12[N_ * 2], pp12[N_ * 2], ss21[N_ * 2], pp21[N_ * 2];
	int d, i, j;
	long long ans, k;
 
	scanf("%d%d", &n, &d);
	for (i = 0; i < n; i++) {
		int x;
 
		scanf("%d%d%lld", &tt[i], &x, &kk[i]);
		if (tt[i] == 1)
			xx[i] = x, yy[i] = x + d;
		else
			xx[i] = x + d, yy[i] = x;
	}
	for (i = 0; i < n; i++)
		ii[i] = i;
	ww = xx, mode = 0, sort(ii, 0, n);
	for (i = 0; i < n; i++)
		xx[ii[i]] = i;
	for (j = 0; j < n; j++)
		jj[j] = j;
	ww = yy, mode = 1, sort(jj, 0, n);
	for (j = 0; j < n; j++)
		yy[jj[j]] = j;
	n_ = 1;
	while (n_ <= n)
		n_ <<= 1;
	ans = 0;
	for (i = 0; i < n; i++) {
		if (tt[i] == 1) {
			update1(st1, xx[i], kk[i]);
			while ((j = query1l(st2, xx[i] + 1)) != -1) {
				j = ii[j];
				k = min(kk[i], kk[j]);
				if (yy[i] < yy[j])
					k = min(k, query2p(ss21, pp21, yy[i], yy[j] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(st1, xx[i], -k);
				update1(st2, xx[j], -k);
				update2(ss12, pp12, xx[i], k), update2(ss12, pp12, xx[j], -k);
				update2(ss21, pp21, yy[j], k), update2(ss21, pp21, yy[i], -k);
				ans += k;
			}
			while ((j = query1r(st2, xx[i] - 1)) != -1) {
				j = ii[j];
				k = min(kk[i], kk[j]);
				k = min(k, query2p(ss12, pp12, xx[j], xx[i] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(st1, xx[i], -k);
				update1(st2, xx[j], -k);
				update2(ss12, pp12, xx[i], k), update2(ss12, pp12, xx[j], -k);
				update2(ss21, pp21, yy[j], k), update2(ss21, pp21, yy[i], -k);
				ans += k;
			}
		} else {
			update1(st2, xx[i], kk[i]);
			while ((j = query1r(st1, xx[i] - 1)) != -1) {
				j = ii[j];
				k = min(kk[i], kk[j]);
				if (yy[j] < yy[i])
					k = min(k, query2p(ss21, pp21, yy[j], yy[i] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(st1, xx[j], -k);
				update1(st2, xx[i], -k);
				update2(ss12, pp12, xx[j], k), update2(ss12, pp12, xx[i], -k);
				update2(ss21, pp21, yy[i], k), update2(ss21, pp21, yy[j], -k);
				ans += k;
			}
			while ((j = query1l(st1, xx[i] + 1)) != -1) {
				j = ii[j];
				k = min(kk[i], kk[j]);
				k = min(k, query2p(ss12, pp12, xx[i], xx[j] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(st1, xx[j], -k);
				update1(st2, xx[i], -k);
				update2(ss12, pp12, xx[j], k), update2(ss12, pp12, xx[i], -k);
				update2(ss21, pp21, yy[i], k), update2(ss21, pp21, yy[j], -k);
				ans += k;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

sugar.c: In function 'main':
sugar.c:128:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d", &n, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~
sugar.c:132:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |   scanf("%d%d%lld", &tt[i], &x, &kk[i]);
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# 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 3 ms 724 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 816 KB Output is correct
13 Correct 5 ms 812 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 4 ms 812 KB Output is correct
17 Correct 4 ms 432 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 816 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 4 ms 436 KB Output is correct
23 Correct 5 ms 852 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 4 ms 852 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 288 KB Output is correct
4 Correct 861 ms 56492 KB Output is correct
5 Correct 445 ms 37540 KB Output is correct
6 Correct 1000 ms 65652 KB Output is correct
7 Correct 479 ms 37804 KB Output is correct
8 Correct 1216 ms 77672 KB Output is correct
9 Correct 981 ms 78132 KB Output is correct
10 Correct 1236 ms 77604 KB Output is correct
11 Correct 960 ms 78028 KB Output is correct
12 Correct 307 ms 33604 KB Output is correct
13 Correct 419 ms 46032 KB Output is correct
14 Correct 699 ms 74672 KB Output is correct
15 Correct 697 ms 74628 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 309 ms 33444 KB Output is correct
3 Correct 449 ms 46060 KB Output is correct
4 Correct 715 ms 74640 KB Output is correct
5 Correct 735 ms 74708 KB Output is correct
6 Correct 677 ms 59940 KB Output is correct
7 Correct 31 ms 5116 KB Output is correct
8 Correct 326 ms 30304 KB Output is correct
9 Correct 545 ms 45264 KB Output is correct
10 Correct 893 ms 75928 KB Output is correct
11 Correct 1002 ms 75932 KB Output is correct
12 Correct 916 ms 76004 KB Output is correct
13 Correct 855 ms 75892 KB Output is correct
14 Correct 920 ms 75916 KB Output is correct
15 Correct 785 ms 75680 KB Output is correct
16 Correct 862 ms 76020 KB Output is correct
17 Correct 1154 ms 76016 KB Output is correct
18 Correct 1185 ms 76036 KB Output is correct
19 Correct 1175 ms 76080 KB Output is correct
20 Correct 1190 ms 76016 KB Output is correct
21 Correct 1167 ms 75860 KB Output is correct
22 Correct 1204 ms 75448 KB Output is correct
23 Correct 1181 ms 74584 KB Output is correct
24 Correct 1022 ms 69520 KB Output is correct
25 Correct 1097 ms 69432 KB Output is correct

Subtask #4
52.0 / 52.0

# 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 3 ms 724 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 428 KB Output is correct
10 Correct 4 ms 852 KB Output is correct
11 Correct 4 ms 852 KB Output is correct
12 Correct 4 ms 816 KB Output is correct
13 Correct 5 ms 812 KB Output is correct
14 Correct 3 ms 512 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 4 ms 812 KB Output is correct
17 Correct 4 ms 432 KB Output is correct
18 Correct 2 ms 468 KB Output is correct
19 Correct 3 ms 816 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 4 ms 436 KB Output is correct
23 Correct 5 ms 852 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 4 ms 852 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 288 KB Output is correct
29 Correct 861 ms 56492 KB Output is correct
30 Correct 445 ms 37540 KB Output is correct
31 Correct 1000 ms 65652 KB Output is correct
32 Correct 479 ms 37804 KB Output is correct
33 Correct 1216 ms 77672 KB Output is correct
34 Correct 981 ms 78132 KB Output is correct
35 Correct 1236 ms 77604 KB Output is correct
36 Correct 960 ms 78028 KB Output is correct
37 Correct 307 ms 33604 KB Output is correct
38 Correct 419 ms 46032 KB Output is correct
39 Correct 699 ms 74672 KB Output is correct
40 Correct 697 ms 74628 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 309 ms 33444 KB Output is correct
43 Correct 449 ms 46060 KB Output is correct
44 Correct 715 ms 74640 KB Output is correct
45 Correct 735 ms 74708 KB Output is correct
46 Correct 677 ms 59940 KB Output is correct
47 Correct 31 ms 5116 KB Output is correct
48 Correct 326 ms 30304 KB Output is correct
49 Correct 545 ms 45264 KB Output is correct
50 Correct 893 ms 75928 KB Output is correct
51 Correct 1002 ms 75932 KB Output is correct
52 Correct 916 ms 76004 KB Output is correct
53 Correct 855 ms 75892 KB Output is correct
54 Correct 920 ms 75916 KB Output is correct
55 Correct 785 ms 75680 KB Output is correct
56 Correct 862 ms 76020 KB Output is correct
57 Correct 1154 ms 76016 KB Output is correct
58 Correct 1185 ms 76036 KB Output is correct
59 Correct 1175 ms 76080 KB Output is correct
60 Correct 1190 ms 76016 KB Output is correct
61 Correct 1167 ms 75860 KB Output is correct
62 Correct 1204 ms 75448 KB Output is correct
63 Correct 1181 ms 74584 KB Output is correct
64 Correct 1022 ms 69520 KB Output is correct
65 Correct 1097 ms 69432 KB Output is correct
66 Correct 624 ms 44920 KB Output is correct
67 Correct 800 ms 53548 KB Output is correct
68 Correct 1047 ms 63348 KB Output is correct
69 Correct 931 ms 57560 KB Output is correct
70 Correct 1022 ms 78880 KB Output is correct
71 Correct 1149 ms 78992 KB Output is correct
72 Correct 1165 ms 78964 KB Output is correct
73 Correct 1248 ms 79092 KB Output is correct
74 Correct 513 ms 33492 KB Output is correct
75 Correct 1016 ms 77956 KB Output is correct
76 Correct 1046 ms 78092 KB Output is correct
77 Correct 566 ms 33432 KB Output is correct
78 Correct 536 ms 33436 KB Output is correct
79 Correct 1321 ms 79060 KB Output is correct
80 Correct 509 ms 33360 KB Output is correct
81 Correct 1259 ms 79040 KB Output is correct
82 Correct 506 ms 33512 KB Output is correct
83 Correct 1612 ms 79284 KB Output is correct
84 Correct 521 ms 33516 KB Output is correct
85 Correct 1318 ms 79196 KB Output is correct
86 Correct 537 ms 33520 KB Output is correct
87 Correct 1350 ms 79212 KB Output is correct
88 Correct 506 ms 33404 KB Output is correct
89 Correct 898 ms 60872 KB Output is correct