oj.uz

Submission #643657

# Submission time Handle Problem Language Result Execution time Memory
643657 2022-09-22T17:44:02 Z rainboy Ants and Sugar (JOI22_sugar) C
26 / 100
 819 ms 50532 KB 
#include <stdio.h>

#define N	500000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */

long long min(long long a, long long b) { return a < b ? a : b; }

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int tt[N], kk[N], xx[N], yy[N], n, 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, int x) {
	i += n_;
	st1[i] += x;
	while (i > 1)
		pul1(i >>= 1);
}

int query1(int r) {
	int l = 0, i;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
		if ((r & 1) == 0) {
			if (st1[r]) {
				i = r;
				while (i < n_)
					i = st1[i << 1 | 1] ? i << 1 | 1 : i << 1 | 0;
				return i - n_;
			}
			r--;
		}
	return -1;
}

long long sum2[N_ * 2], pref2[N_ * 2];

void pul2(int i) {
	int l = i << 1, r = l | 1;

	sum2[i] = sum2[l] + sum2[r];
	pref2[i] = min(pref2[l], sum2[l] + pref2[r]);
}

void update2(int i, int x) {
	i += n_;
	sum2[i] += x, pref2[i] = min(sum2[i], 0);
	while (i > 1)
		pul2(i >>= 1);
}

long long query2(int l, int r) {
	long long sum = 0;

	for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			sum += sum2[l++];
		if ((r & 1) == 0)
			sum += sum2[r--];
	}
	return sum;
}

long long query3(int l, int r) {
	long long s = query2(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 + pref2[l]), sl += sum2[l], l++;
		if ((r & 1) == 0)
			pr = min(pref2[r], sum2[r] + pr), r--;
	}
	return s + min(pl, sl + pr);
}

int main() {
	static int ii[N], jj[N];
	int d, i, j, k;
	long long ans;

	scanf("%d%d", &n, &d);
	for (i = 0; i < n; i++) {
		int x;

		scanf("%d%d%d", &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;
	for (i = 0; i < n; i++)
		if (tt[i] == 1)
			update1(xx[i], kk[i]);
	ans = 0;
	for (j = 0; j < n; j++) {
		if (tt[j] == 2)
			while (1) {
				i = query1(xx[j] - 1);
				if (i == -1)
					break;
				i = ii[i];
				k = min(kk[i], kk[j]);
				if (yy[j] > yy[i])
					k = min(k, query3(yy[i], yy[j] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(xx[i], -k);
				update2(yy[i], -k), update2(yy[j], k);
				ans += k;
			}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 220 ms 21928 KB Output is correct
3 Correct 301 ms 30284 KB Output is correct
4 Correct 462 ms 49164 KB Output is correct
5 Correct 544 ms 49136 KB Output is correct
6 Correct 497 ms 39324 KB Output is correct
7 Correct 24 ms 3404 KB Output is correct
8 Correct 226 ms 19920 KB Output is correct
9 Correct 426 ms 29700 KB Output is correct
10 Correct 663 ms 50424 KB Output is correct
11 Correct 707 ms 50532 KB Output is correct
12 Correct 624 ms 50464 KB Output is correct
13 Correct 622 ms 50436 KB Output is correct
14 Correct 632 ms 50380 KB Output is correct
15 Correct 563 ms 50084 KB Output is correct
16 Correct 603 ms 50360 KB Output is correct
17 Correct 780 ms 50416 KB Output is correct
18 Correct 773 ms 50476 KB Output is correct
19 Correct 734 ms 50484 KB Output is correct
20 Correct 738 ms 50428 KB Output is correct
21 Correct 786 ms 50448 KB Output is correct
22 Correct 746 ms 50124 KB Output is correct
23 Correct 819 ms 49736 KB Output is correct
24 Correct 672 ms 47304 KB Output is correct
25 Correct 767 ms 47176 KB Output is correct

Subtask #4
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -