oj.uz

Submission #467569

# Submission time Handle Problem Language Result Execution time Memory
467569 2021-08-23T17:29:16 Z rainboy Distributing Candies (IOI21_candies) C++17
100 / 100
 415 ms 26780 KB 
#include "candies.h"
#include <vector>

using namespace std;

typedef vector<int> vi;

const int Q = 200000, N_ = 1 << 18;	/* N_ = pow2(ceil(log(Q))) */

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 xx[Q * 2], hh[Q * 2];

void sort(int *hh, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, h = hh[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (xx[hh[j]] == xx[h])
				j++;
			else if (xx[hh[j]] < xx[h]) {
				tmp = hh[i], hh[i] = hh[j], hh[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = hh[j], hh[j] = hh[k], hh[k] = tmp;
			}
		sort(hh, l, i);
		l = k;
	}
}

long long sum[N_ * 2], mn[N_ * 2], mx[N_ * 2]; int n_;

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

	sum[i] = sum[l] + sum[r];
	mn[i] = min(mn[r], mn[l] + sum[r]);
	mx[i] = max(mx[r], mx[l] + sum[r]);
}

void update(int i, int x) {
	i += n_;
	sum[i] = x, mn[i] = min(x, 0), mx[i] = max(x, 0);
	while (i > 1)
		pul(i >>= 1);
}

int query(int c) {
	int i;
	long long s, x, y;

	if (mx[1] - mn[1] <= c)
		return mx[1];
	i = 1, s = 0, x = 0, y = 0;
	while (i < n_) {
		long long s_ = sum[i << 1 | 1] + s, x_ = min(x, mn[i << 1 | 1] + s), y_ = max(y, mx[i << 1 | 1] + s);

		if (y_ - x_ <= c) {
			i = i << 1 | 0;
			s = s_, x = x_, y = y_;
		} else
			i = i << 1 | 1;
	}
	return min(max(sum[i] + s, y), c + x);
}

vi distribute_candies(vi cc, vi ll, vi rr, vi vv) {
	int n = cc.size(), q = ll.size(), h, i;
	vi aa(n);

	for (h = 0; h < q; h++)
		xx[h << 1 | 0] = ll[h], xx[h << 1 | 1] = rr[h] + 1;
	n_ = 1;
	while (n_ < q)
		n_ <<= 1;
	for (h = 0; h < q * 2; h++)
		hh[h] = h;
	sort(hh, 0, q * 2);
	for (i = 0, h = 0; i < n; i++) {
		while (h < q * 2 && xx[hh[h]] <= i)
			update(hh[h] >> 1, (hh[h] & 1) == 0 ? vv[hh[h] >> 1] : 0), h++;
		aa[i] = query(cc[i]);
	}
	return aa;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 280 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 19940 KB Output is correct
2 Correct 374 ms 19944 KB Output is correct
3 Correct 366 ms 19944 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 232 ms 20428 KB Output is correct
3 Correct 85 ms 6044 KB Output is correct
4 Correct 385 ms 23284 KB Output is correct
5 Correct 354 ms 26256 KB Output is correct
6 Correct 369 ms 26780 KB Output is correct
7 Correct 415 ms 25892 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 97 ms 20200 KB Output is correct
4 Correct 71 ms 4108 KB Output is correct
5 Correct 171 ms 22800 KB Output is correct
6 Correct 177 ms 24128 KB Output is correct
7 Correct 185 ms 24648 KB Output is correct
8 Correct 166 ms 23236 KB Output is correct
9 Correct 194 ms 24772 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 280 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 2 ms 460 KB Output is correct
5 Correct 3 ms 460 KB Output is correct
6 Correct 375 ms 19940 KB Output is correct
7 Correct 374 ms 19944 KB Output is correct
8 Correct 366 ms 19944 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 232 ms 20428 KB Output is correct
11 Correct 85 ms 6044 KB Output is correct
12 Correct 385 ms 23284 KB Output is correct
13 Correct 354 ms 26256 KB Output is correct
14 Correct 369 ms 26780 KB Output is correct
15 Correct 415 ms 25892 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 97 ms 20200 KB Output is correct
19 Correct 71 ms 4108 KB Output is correct
20 Correct 171 ms 22800 KB Output is correct
21 Correct 177 ms 24128 KB Output is correct
22 Correct 185 ms 24648 KB Output is correct
23 Correct 166 ms 23236 KB Output is correct
24 Correct 194 ms 24772 KB Output is correct
25 Correct 0 ms 284 KB Output is correct
26 Correct 68 ms 4060 KB Output is correct
27 Correct 217 ms 20224 KB Output is correct
28 Correct 342 ms 24496 KB Output is correct
29 Correct 345 ms 24852 KB Output is correct
30 Correct 356 ms 25156 KB Output is correct
31 Correct 352 ms 25156 KB Output is correct
32 Correct 362 ms 25540 KB Output is correct