oj.uz

Submission #643695

# Submission time Handle Problem Language Result Execution time Memory
643695 2022-09-22T19:19:54 Z rainboy Ants and Sugar (JOI22_sugar) C
32 / 100
 4000 ms 73784 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 = -1;
	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 (i == -1)
		return -1;
	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 = -1;
	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 (i == -1)
		return -1;
	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 query12p(int l, int r) {
	long long 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 min(pl, sl + pr);
}

long long query12q(int l, int r) {
	long long sr = 0, ql = 0, qr = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			ql = max(sum12[l] + ql, suf12[l]), l++;
		if ((r & 1) == 0)
			qr = max(qr, sr + suf12[r]), sr += sum12[r], r--;
	}
	return max(qr, sr + ql);
}

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, 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(xx[i] + 1);
				if (j == -1)
					break;
				j = ii[j];
				k = min(kk[i], kk[j]);
				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;
			}
			while (1) {
				i_ = query12r(xx[i] - 1);
				if (i_ == -1)
					break;
				i_ = ii[i_];
				k = min(kk[i], query12q(xx[i_], xx[i] - 1) - query12q(xx[i_] + 1, xx[i] - 1));
				if (k == 0)
					break;
				if (i == i_)
					return 0;
				kk[i] -= k, kk[i_] += k;
				update2(xx[i_], k), update2(xx[i], -k);
				update12(xx[i_], -k), update12(xx[i], k);
				update21(yy[i_], k), update21(yy[i], -k);
			}
		} else {
			update1(xx[i], kk[i]);
			while (1) {
				j = query2(xx[i] - 1);
				if (j == -1)
					break;
				j = ii[j];
				k = min(kk[i], kk[j]);
				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;
			}
			while (1) {
				i_ = query12l(xx[i] + 1);
				if (i_ == -1)
					break;
				i_ = ii[i_];
				k = min(kk[i], query12p(xx[i] + 1, xx[i_] - 1) - query12p(xx[i] + 1, xx[i_]));
				if (k == 0)
					break;
				kk[i] -= k, kk[i_] += k;
				update1(xx[i_], k), update1(xx[i], -k);
				update12(xx[i_], k), update12(xx[i], -k);
				update21(yy[i_], -k), update21(yy[i], 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 2 ms 724 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 820 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 3 ms 520 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 6 ms 944 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 7 ms 908 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 7 ms 812 KB Output is correct

Subtask #2
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 867 ms 55468 KB Output is correct
5 Execution timed out 4080 ms 15956 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 335 ms 32932 KB Output is correct
3 Correct 479 ms 45164 KB Output is correct
4 Correct 789 ms 73428 KB Output is correct
5 Correct 791 ms 73772 KB Output is correct
6 Correct 752 ms 59428 KB Output is correct
7 Correct 34 ms 5452 KB Output is correct
8 Correct 366 ms 30408 KB Output is correct
9 Correct 637 ms 44856 KB Output is correct
10 Correct 1041 ms 73576 KB Output is correct
11 Correct 1193 ms 73640 KB Output is correct
12 Correct 1067 ms 73644 KB Output is correct
13 Correct 895 ms 73548 KB Output is correct
14 Correct 1012 ms 73640 KB Output is correct
15 Correct 719 ms 73364 KB Output is correct
16 Correct 886 ms 73540 KB Output is correct
17 Correct 1342 ms 73784 KB Output is correct
18 Correct 1326 ms 73676 KB Output is correct
19 Correct 1331 ms 73724 KB Output is correct
20 Correct 1332 ms 73652 KB Output is correct
21 Correct 1295 ms 73680 KB Output is correct
22 Correct 1293 ms 73364 KB Output is correct
23 Correct 1296 ms 72248 KB Output is correct
24 Correct 1175 ms 67300 KB Output is correct
25 Correct 1259 ms 67008 KB Output is correct

Subtask #4
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 2 ms 724 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 3 ms 852 KB Output is correct
11 Correct 3 ms 852 KB Output is correct
12 Correct 5 ms 852 KB Output is correct
13 Correct 4 ms 852 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 3 ms 820 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 3 ms 468 KB Output is correct
18 Correct 3 ms 520 KB Output is correct
19 Correct 3 ms 852 KB Output is correct
20 Correct 3 ms 468 KB Output is correct
21 Correct 6 ms 944 KB Output is correct
22 Correct 3 ms 468 KB Output is correct
23 Correct 7 ms 908 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 7 ms 812 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 867 ms 55468 KB Output is correct
30 Execution timed out 4080 ms 15956 KB Time limit exceeded
31 Halted 0 ms 0 KB -