oj.uz

답안 #643715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
643715 2022-09-22T19:29:32 Z rainboy Ants and Sugar (JOI22_sugar) C
26 / 100
 941 ms 50408 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 sum3[N_ * 2], pref3[N_ * 2];

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

	sum3[i] = sum3[l] + sum3[r];
	pref3[i] = min(pref3[l], sum3[l] + pref3[r]);
}

void update3(int i, long long x) {
	i += n_;
	sum3[i] += x, pref3[i] = min(sum3[i], 0);
	while (i > 1)
		pul3(i >>= 1);
}

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

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

long long query3p(int l, int r) {
	long long s = query3s(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 + pref3[l]), sl += sum3[l], l++;
		if ((r & 1) == 0)
			pr = min(pref3[r], sum3[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(xx[i] + 1);
				if (j == -1)
					break;
				j = ii[j];
				k = min(kk[i], kk[j]);
				if (yy[i] < yy[j])
					k = min(k, query3p(yy[i], yy[j] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(xx[j], -k);
				update2(xx[i], -k);
				update3(yy[j], k), update3(yy[i], -k);
				ans += 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, query3p(yy[j], yy[i] - 1));
				if (k == 0)
					break;
				kk[i] -= k, kk[j] -= k;
				update1(xx[i], -k);
				update2(xx[j], -k);
				update3(yy[i], k), update3(yy[j], -k);
				ans += k;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 225 ms 22852 KB Output is correct
3 Correct 316 ms 31168 KB Output is correct
4 Correct 521 ms 50264 KB Output is correct
5 Correct 507 ms 50408 KB Output is correct
6 Correct 559 ms 40580 KB Output is correct
7 Correct 27 ms 3788 KB Output is correct
8 Correct 266 ms 20904 KB Output is correct
9 Correct 461 ms 30788 KB Output is correct
10 Correct 740 ms 50052 KB Output is correct
11 Correct 787 ms 50128 KB Output is correct
12 Correct 752 ms 50128 KB Output is correct
13 Correct 743 ms 50032 KB Output is correct
14 Correct 762 ms 50148 KB Output is correct
15 Correct 617 ms 49796 KB Output is correct
16 Correct 691 ms 49996 KB Output is correct
17 Correct 897 ms 50108 KB Output is correct
18 Correct 941 ms 50332 KB Output is correct
19 Correct 901 ms 50092 KB Output is correct
20 Correct 916 ms 50104 KB Output is correct
21 Correct 929 ms 50196 KB Output is correct
22 Correct 894 ms 49628 KB Output is correct
23 Correct 919 ms 48660 KB Output is correct
24 Correct 833 ms 43608 KB Output is correct
25 Correct 891 ms 43504 KB Output is correct

Subtask #4
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -