oj.uz

Submission #435099

# Submission time Handle Problem Language Result Execution time Memory
435099 2021-06-23T02:36:02 Z Elegia Distributing Candies (IOI21_candies) C++17
0 / 100
 507 ms 32844 KB 
#include "candies.h"

#include <algorithm>
#include <iostream>
#include <vector>

using ll = long long;

const int INF = int(1e9) + 1;
const int N = 1 << 18, SZ = N << 1;

ll sum[SZ], minv[SZ], maxv[SZ];

void change(int o, int l, int r, int k, int v) {
	if (l == r) {
		sum[o] = v;
		minv[o] = std::min(v, 0);
		maxv[o] = std::max(v, 0);
		return;
	}
	int mid = (l + r) / 2;
	if (k <= mid) change(o << 1, l, mid, k, v);
	else change(o << 1 | 1, mid + 1, r, k, v);

	sum[o] = sum[o << 1] + sum[o << 1 | 1];
	minv[o] = std::min(minv[o], sum[o << 1] + minv[o << 1 | 1]);
	maxv[o] = std::max(maxv[o], sum[o << 1] + maxv[o << 1 | 1]);
}

std::vector<std::pair<int, int>> modify[N];

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
	int n = c.size(), m = l.size();
	for (int i = 0; i != m; ++i) {
		modify[l[i]].emplace_back(i + 2, v[i]);
		modify[r[i] + 1].emplace_back(i + 2, 0);
	}
	m += 1;
	change(1, 0, m, 0, -INF);
	change(1, 0, m, 1, INF);

	std::vector<int> ans(n);
	for (int i = 0; i != n; ++i) {
		for (const auto& [k, v] : modify[i])
			change(1, 0, m, k, v);
		ll vl = sum[1], vr = sum[1], s = 0;
		int o = 1, l = 0, r = m;
		while (l != r) {
			int mid = (l + r) / 2;
			ll nl = std::min(vl, sum[o << 1] + minv[o << 1 | 1]),
			   nr = std::max(vr, sum[o << 1] + maxv[o << 1 | 1]);
			if (nr - nl > c[i]) {
				s += sum[o << 1];
				o = o << 1 | 1;
				l = mid + 1;
			} else {
				vl = nl;
				vr = nr;
				o = o << 1;
				r = mid;
			}
		}
		if (s <= vl)
			ans[i] = c[i] - (vr - sum[1]);
		else
			ans[i] = sum[1] - vl;
	}
	return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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