oj.uz

Submission #643734

# Submission time Handle Problem Language Result Execution time Memory
643734 2022-09-22T19:46:25 Z rainboy Ants and Sugar (JOI22_sugar) C
26 / 100
 1356 ms 74640 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 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, 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 (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 (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
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 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 Incorrect 4 ms 724 KB Output isn't correct
7 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 Correct 1 ms 288 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Incorrect 1243 ms 56588 KB Output isn't correct
5 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 394 ms 33960 KB Output is correct
3 Correct 548 ms 46392 KB Output is correct
4 Correct 914 ms 74356 KB Output is correct
5 Correct 908 ms 74592 KB Output is correct
6 Correct 745 ms 60152 KB Output is correct
7 Correct 40 ms 5628 KB Output is correct
8 Correct 357 ms 31148 KB Output is correct
9 Correct 638 ms 45684 KB Output is correct
10 Correct 974 ms 74328 KB Output is correct
11 Correct 1074 ms 74444 KB Output is correct
12 Correct 982 ms 74372 KB Output is correct
13 Correct 899 ms 74472 KB Output is correct
14 Correct 979 ms 74424 KB Output is correct
15 Correct 718 ms 74172 KB Output is correct
16 Correct 890 ms 74640 KB Output is correct
17 Correct 1356 ms 74448 KB Output is correct
18 Correct 1330 ms 74540 KB Output is correct
19 Correct 1330 ms 74404 KB Output is correct
20 Correct 1350 ms 74472 KB Output is correct
21 Correct 1353 ms 74560 KB Output is correct
22 Correct 1307 ms 74004 KB Output is correct
23 Correct 1304 ms 72972 KB Output is correct
24 Correct 1167 ms 68008 KB Output is correct
25 Correct 1248 ms 67776 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 1 ms 340 KB Output is correct
3 Correct 1 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 Incorrect 4 ms 724 KB Output isn't correct
7 Halted 0 ms 0 KB -