oj.uz

Submission #1017663

# Submission time Handle Problem Language Result Execution time Memory
1017663 2024-07-09T09:24:19 Z aykhn Distributing Candies (IOI21_candies) C++17
100 / 100
 1022 ms 49376 KB 
#include "candies.h"
#include <bits/stdc++.h>

using namespace std;

#define inf 0x3F3F3F3F3F3F3F3F

const int MXN = 2e5 + 5;

array<long long, 2> st[MXN << 2];
long long lz[MXN << 2];
vector<array<long long, 2>> add[MXN], del[MXN];

array<long long, 2> combine(array<long long, 2> x, array<long long, 2> y)
{
	return {min(x[0], y[0]), max(x[1], y[1])};
}
void relax(int l, int r, int x)
{
	if (!lz[x]) return;
	st[x][0] += lz[x], st[x][1] += lz[x];
	if (l == r)
	{
		lz[x] = 0;
		return;
	}
	lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
	lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] += val;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	upd(l, mid, 2*x, lx, rx, val);
	upd(mid + 1, r, 2*x + 1, lx, rx, val);
	st[x] = combine(st[2*x], st[2*x + 1]);
}
array<long long, 2> get(int l, int r, int x, int lx, int rx)
{
	if (l > rx || r < lx) return {inf, -inf};
	relax(l, r, x);
	if (l >= lx && r <= rx) return st[x];
	int mid = (l + r) >> 1;
	return combine(get(l, mid, 2*x, lx, rx), get(mid + 1, r, 2*x + 1, lx, rx));
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) 
{
	int n = c.size(), q = l.size();
	for (int i = 0; i < q; i++)
	{
		add[l[i]].push_back({i + 1, v[i]});
		del[r[i]].push_back({i + 1, v[i]});
	}
	vector<int> res(n);
	for (int i = 0; i < n; i++)
	{
		for (array<long long, 2> &x : add[i]) upd(0, q, 1, x[0], q, x[1]);
		array<long long, 2> a = get(0, q, 1, 0, q);
		long long val = get(0, q, 1, q, q)[0];
		if (a[1] - a[0] <= c[i])
		{
			res[i] = val - a[0];
			for (array<long long, 2> &x : del[i]) upd(0, q, 1, x[0], q, -x[1]);
			continue;
		}
		int l = 0, r = q;
		while (l < r)
		{
			int mid = (l + r + 1) >> 1;
			array<long long, 2> x = get(0, q, 1, mid, q);
			if (x[1] - x[0] > c[i]) l = mid;
			else r = mid - 1;
		}
		array<long long, 2> f = get(0, q, 1, l, l);
		array<long long, 2> p = get(0, q, 1, l, q);
		if (f[0] == p[0]) res[i] = (val - (p[1] - c[i]));
		else if (f[0] == p[1]) res[i] = (val - p[0]);
		else assert(0);
		for (array<long long, 2> &x : del[i]) upd(0, q, 1, x[0], q, -x[1]);
	}
	return res;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 10 ms 13148 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 871 ms 42700 KB Output is correct
2 Correct 878 ms 46756 KB Output is correct
3 Correct 793 ms 46672 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 166 ms 43564 KB Output is correct
3 Correct 261 ms 16708 KB Output is correct
4 Correct 962 ms 48644 KB Output is correct
5 Correct 994 ms 49080 KB Output is correct
6 Correct 1022 ms 49376 KB Output is correct
7 Correct 971 ms 48812 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 2 ms 12732 KB Output is correct
3 Correct 134 ms 39096 KB Output is correct
4 Correct 223 ms 16612 KB Output is correct
5 Correct 642 ms 41940 KB Output is correct
6 Correct 649 ms 43736 KB Output is correct
7 Correct 748 ms 43340 KB Output is correct
8 Correct 543 ms 41988 KB Output is correct
9 Correct 709 ms 44204 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12888 KB Output is correct
2 Correct 2 ms 12892 KB Output is correct
3 Correct 3 ms 12892 KB Output is correct
4 Correct 4 ms 12892 KB Output is correct
5 Correct 10 ms 13148 KB Output is correct
6 Correct 871 ms 42700 KB Output is correct
7 Correct 878 ms 46756 KB Output is correct
8 Correct 793 ms 46672 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Correct 166 ms 43564 KB Output is correct
11 Correct 261 ms 16708 KB Output is correct
12 Correct 962 ms 48644 KB Output is correct
13 Correct 994 ms 49080 KB Output is correct
14 Correct 1022 ms 49376 KB Output is correct
15 Correct 971 ms 48812 KB Output is correct
16 Correct 2 ms 12892 KB Output is correct
17 Correct 2 ms 12732 KB Output is correct
18 Correct 134 ms 39096 KB Output is correct
19 Correct 223 ms 16612 KB Output is correct
20 Correct 642 ms 41940 KB Output is correct
21 Correct 649 ms 43736 KB Output is correct
22 Correct 748 ms 43340 KB Output is correct
23 Correct 543 ms 41988 KB Output is correct
24 Correct 709 ms 44204 KB Output is correct
25 Correct 2 ms 12888 KB Output is correct
26 Correct 157 ms 14612 KB Output is correct
27 Correct 159 ms 43348 KB Output is correct
28 Correct 628 ms 47148 KB Output is correct
29 Correct 691 ms 47720 KB Output is correct
30 Correct 862 ms 47908 KB Output is correct
31 Correct 782 ms 47956 KB Output is correct
32 Correct 818 ms 48056 KB Output is correct