oj.uz

답안 #1017651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1017651 2024-07-09T09:20:12 Z aykhn 사탕 분배 (IOI21_candies) C++17
0 / 100
 887 ms 44532 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]);
		long long val = get(0, q, 1, q, q)[0];
		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
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Runtime error 10 ms 19548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 887 ms 44532 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 19548 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 9820 KB Output is correct
2 Runtime error 10 ms 19548 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -