oj.uz

Submission #643743

# Submission time Handle Problem Language Result Execution time Memory
643743 2022-09-22T20:19:00 Z rainboy Ants and Sugar (JOI22_sugar) C
100 / 100
 1836 ms 87308 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;
	}
}
 
long long st1[N_ * 2];
 
void pul1(int i) {
	st1[i] = st1[i << 1 | 0] + st1[i << 1 | 1];
}
 
void update1(int i, long long x) {
	i += n_;
	st1[i] += x;
	while (i > 1)
		pul1(i >>= 1);
}
 
int query1(int l) {
	int r = n_ - 1, i;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st1[l]) {
				i = l;
				while (i < n_)
					i = st1[i << 1 | 0] ? i << 1 | 0 : i << 1 | 1;
				return i - n_;
			}
			l++;
		}
	return -1;
}
 
long long st2[N_ * 2];
 
void pul2(int i) {
	st2[i] = st2[i << 1 | 0] + st2[i << 1 | 1];
}
 
void update2(int i, long long x) {
	i += n_;
	st2[i] += x;
	while (i > 1)
		pul2(i >>= 1);
}
 
int query2(int r) {
	int l = 0, i;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st2[r]) {
				i = r;
				while (i < n_)
					i = st2[i << 1 | 1] ? i << 1 | 1 : i << 1 | 0;
				return i - n_;
			}
			r--;
		}
	return -1;
}
 
long long sum12[N_ * 2], pref12[N_ * 2], suf12[N_ * 2];
 
void pul12(int i) {
	int l = i << 1, r = l | 1;
 
	sum12[i] = sum12[l] + sum12[r];
	pref12[i] = min(pref12[l], sum12[l] + pref12[r]);
	suf12[i] = max(suf12[r], sum12[r] + suf12[l]);
}
 
void update12(int i, long long x) {
	i += n_;
	sum12[i] += x, pref12[i] = min(sum12[i], 0), suf12[i] = max(sum12[i], 0);
	while (i > 1)
		pul12(i >>= 1);
}
 
int query12l(int l) {
	int r = n_ - 1, i;
	long long s, p;
 
	s = 0, p = 0, i = l;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (p > s + pref12[l])
				p = s + pref12[l], i = l;
			s += sum12[l];
			l++;
		}
	if (p == 0)
		return i;
	while (i < n_)
		i = pref12[i << 1 | 0] <= sum12[i << 1 | 0] + pref12[i << 1 | 1] ? i << 1 | 0 : i << 1 | 1;
	return i - n_;
}
 
int query12r(int r) {
	int l = 0, i;
	long long s, q;
 
	s = 0, q = 0, i = r;
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (q < s + suf12[r])
				q = s + suf12[r], i = r;
			s += sum12[r];
			r--;
		}
	if (q == 0)
		return i;
	while (i < n_)
		i = suf12[i << 1 | 1] >= sum12[i << 1 | 1] + suf12[i << 1 | 0] ? i << 1 | 1 : i << 1 | 0;
	return i - n_;
}
 
long long query12s(int l, int r) {
	long long sum = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			sum += sum12[l++];
		if ((r & 1) == 0)
			sum += sum12[r--];
	}
	return sum;
}
 
long long query12p(int l, int r) {
	long long s = query12s(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 + pref12[l]), sl += sum12[l], l++;
		if ((r & 1) == 0)
			pr = min(pref12[r], sum12[r] + pr), r--;
	}
	return s + min(pl, sl + pr);
}
 
long long sum21[N_ * 2], pref21[N_ * 2];
 
void pul21(int i) {
	int l = i << 1, r = l | 1;
 
	sum21[i] = sum21[l] + sum21[r];
	pref21[i] = min(pref21[l], sum21[l] + pref21[r]);
}
 
void update21(int i, long long x) {
	i += n_;
	sum21[i] += x, pref21[i] = min(sum21[i], 0);
	while (i > 1)
		pul21(i >>= 1);
}
 
long long query21s(int l, int r) {
	long long sum = 0;
 
	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			sum += sum21[l++];
		if ((r & 1) == 0)
			sum += sum21[r--];
	}
	return sum;
}
 
long long query21p(int l, int r) {
	long long s = query21s(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 + pref21[l]), sl += sum21[l], l++;
		if ((r & 1) == 0)
			pr = min(pref21[r], sum21[r] + pr), r--;
	}
	return s + min(pl, sl + pr);
}
 
int main() {
	static int ii[N], jj[N];
	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) {
			update2(xx[i], kk[i]);
			while (1) {
				j = query1(query12r(xx[i]) + 1);
				if (j == -1)
					break;
				j = ii[j];
				k = min(kk[i], kk[j]);
				if (xx[i] > xx[j])
					k = min(k, query12p(xx[j], xx[i] - 1));
				if (yy[i] < yy[j])
					k = min(k, query21p(yy[i], yy[j] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(xx[j], -k);
				update2(xx[i], -k);
				update12(xx[i], k), update12(xx[j], -k);
				update21(yy[j], k), update21(yy[i], -k);
				ans += k;
			}
		} else {
			update1(xx[i], kk[i]);
			while (1) {
				j = query2(query12l(xx[i]) - 1);
				if (j == -1)
					break;
				j = ii[j];
				k = min(kk[i], kk[j]);
				if (xx[i] < xx[j])
					k = min(k, query12p(xx[i], xx[j] - 1));
				if (yy[i] > yy[j])
					k = min(k, query21p(yy[j], yy[i] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(xx[i], -k);
				update2(xx[j], -k);
				update12(xx[j], k), update12(xx[i], -k);
				update21(yy[i], k), update21(yy[j], -k);
				ans += k;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

sugar.c: In function 'main':
sugar.c:223:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |  scanf("%d%d", &n, &d);
      |  ^~~~~~~~~~~~~~~~~~~~~
sugar.c:227:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  227 |   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 768 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 432 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 4 ms 944 KB Output is correct
12 Correct 4 ms 904 KB Output is correct
13 Correct 5 ms 852 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 3 ms 812 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 7 ms 940 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 5 ms 856 KB Output is correct

Subtask #2
16.0 / 16.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 821 ms 55624 KB Output is correct
5 Correct 539 ms 37792 KB Output is correct
6 Correct 1156 ms 72032 KB Output is correct
7 Correct 539 ms 41592 KB Output is correct
8 Correct 1171 ms 85488 KB Output is correct
9 Correct 1192 ms 85852 KB Output is correct
10 Correct 1189 ms 85300 KB Output is correct
11 Correct 1217 ms 85824 KB Output is correct
12 Correct 382 ms 36940 KB Output is correct
13 Correct 565 ms 50860 KB Output is correct
14 Correct 912 ms 82456 KB Output is correct
15 Correct 961 ms 82400 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 434 ms 32808 KB Output is correct
3 Correct 523 ms 45196 KB Output is correct
4 Correct 898 ms 73220 KB Output is correct
5 Correct 891 ms 73372 KB Output is correct
6 Correct 700 ms 58872 KB Output is correct
7 Correct 34 ms 4944 KB Output is correct
8 Correct 330 ms 29812 KB Output is correct
9 Correct 634 ms 44344 KB Output is correct
10 Correct 985 ms 73084 KB Output is correct
11 Correct 1102 ms 73192 KB Output is correct
12 Correct 990 ms 73116 KB Output is correct
13 Correct 907 ms 73080 KB Output is correct
14 Correct 1006 ms 73160 KB Output is correct
15 Correct 751 ms 72820 KB Output is correct
16 Correct 907 ms 73036 KB Output is correct
17 Correct 1303 ms 73224 KB Output is correct
18 Correct 1324 ms 73116 KB Output is correct
19 Correct 1322 ms 73148 KB Output is correct
20 Correct 1383 ms 73104 KB Output is correct
21 Correct 1290 ms 73208 KB Output is correct
22 Correct 1304 ms 72644 KB Output is correct
23 Correct 1291 ms 71616 KB Output is correct
24 Correct 1178 ms 66684 KB Output is correct
25 Correct 1218 ms 66672 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 768 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 432 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 4 ms 944 KB Output is correct
12 Correct 4 ms 904 KB Output is correct
13 Correct 5 ms 852 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Correct 3 ms 812 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 2 ms 468 KB Output is correct
18 Correct 3 ms 468 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 5 ms 852 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 7 ms 940 KB Output is correct
24 Correct 3 ms 468 KB Output is correct
25 Correct 5 ms 856 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 821 ms 55624 KB Output is correct
30 Correct 539 ms 37792 KB Output is correct
31 Correct 1156 ms 72032 KB Output is correct
32 Correct 539 ms 41592 KB Output is correct
33 Correct 1171 ms 85488 KB Output is correct
34 Correct 1192 ms 85852 KB Output is correct
35 Correct 1189 ms 85300 KB Output is correct
36 Correct 1217 ms 85824 KB Output is correct
37 Correct 382 ms 36940 KB Output is correct
38 Correct 565 ms 50860 KB Output is correct
39 Correct 912 ms 82456 KB Output is correct
40 Correct 961 ms 82400 KB Output is correct
41 Correct 0 ms 340 KB Output is correct
42 Correct 434 ms 32808 KB Output is correct
43 Correct 523 ms 45196 KB Output is correct
44 Correct 898 ms 73220 KB Output is correct
45 Correct 891 ms 73372 KB Output is correct
46 Correct 700 ms 58872 KB Output is correct
47 Correct 34 ms 4944 KB Output is correct
48 Correct 330 ms 29812 KB Output is correct
49 Correct 634 ms 44344 KB Output is correct
50 Correct 985 ms 73084 KB Output is correct
51 Correct 1102 ms 73192 KB Output is correct
52 Correct 990 ms 73116 KB Output is correct
53 Correct 907 ms 73080 KB Output is correct
54 Correct 1006 ms 73160 KB Output is correct
55 Correct 751 ms 72820 KB Output is correct
56 Correct 907 ms 73036 KB Output is correct
57 Correct 1303 ms 73224 KB Output is correct
58 Correct 1324 ms 73116 KB Output is correct
59 Correct 1322 ms 73148 KB Output is correct
60 Correct 1383 ms 73104 KB Output is correct
61 Correct 1290 ms 73208 KB Output is correct
62 Correct 1304 ms 72644 KB Output is correct
63 Correct 1291 ms 71616 KB Output is correct
64 Correct 1178 ms 66684 KB Output is correct
65 Correct 1218 ms 66672 KB Output is correct
66 Correct 601 ms 49376 KB Output is correct
67 Correct 770 ms 58776 KB Output is correct
68 Correct 1056 ms 69780 KB Output is correct
69 Correct 1018 ms 63572 KB Output is correct
70 Correct 1004 ms 86640 KB Output is correct
71 Correct 1049 ms 86700 KB Output is correct
72 Correct 1171 ms 86864 KB Output is correct
73 Correct 1243 ms 86932 KB Output is correct
74 Correct 503 ms 33472 KB Output is correct
75 Correct 918 ms 85868 KB Output is correct
76 Correct 812 ms 85948 KB Output is correct
77 Correct 526 ms 33580 KB Output is correct
78 Correct 538 ms 33524 KB Output is correct
79 Correct 1310 ms 86876 KB Output is correct
80 Correct 519 ms 33436 KB Output is correct
81 Correct 1297 ms 87020 KB Output is correct
82 Correct 516 ms 33580 KB Output is correct
83 Correct 1836 ms 87308 KB Output is correct
84 Correct 545 ms 33480 KB Output is correct
85 Correct 1658 ms 87052 KB Output is correct
86 Correct 520 ms 33484 KB Output is correct
87 Correct 1603 ms 87056 KB Output is correct
88 Correct 507 ms 33468 KB Output is correct
89 Correct 1002 ms 65128 KB Output is correct