oj.uz

Submission #467568

# Submission time Handle Problem Language Result Execution time Memory
467568 2021-08-23T17:19:52 Z rainboy Distributing Candies (IOI21_candies) C++17
8 / 100
 368 ms 24004 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[l], sum[l] + mn[r]);
	mx[i] = max(mx[l], sum[l] + mx[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 0 + sum[1] - mn[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, 0 + s - x), c + s - y);
}

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
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 23252 KB Output is correct
2 Correct 368 ms 24004 KB Output is correct
3 Correct 345 ms 23860 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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