Submission #644994

#	Time	Username	Problem	Language	Result	Execution time	Memory
644994		rainboy	Ants and Sugar (JOI22_sugar)	C11	100 / 100	1612 ms	79284 KiB

sugar

#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 (stderr)

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 / 6
• Subtask 2: 16 / 16
• Subtask 3: 26 / 26
• Subtask 4: 52 / 52