oj.uz

답안 #838307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838307 2023-08-26T14:16:34 Z happypotato 사탕 분배 (IOI21_candies) C++17
0 / 100
 367 ms 46460 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back

const int mxN = 2e5 + 1;
struct info {
	int net; // net change
	int mini, maxi;
	info(): net(0), mini(1e18), maxi(-1e18) {};
	info(int val): net(val), mini(val), maxi(val) {};
};
info merge(info &lhs, info &rhs) {
	info res;
	res.net = lhs.net + rhs.net;
	res.mini = min(lhs.mini, min(0LL, lhs.net) + rhs.mini);
	res.maxi = max(lhs.maxi, max(0LL, lhs.net) + rhs.maxi);
	return res;
}
info EMPTY = info();
info ZERO = info(0);
info seg[4 * mxN];
int lazy[4 * mxN];
int n, q;
void build(int l = 0, int r = q, int idx = 1) {
	if (l == r) {
		if (l == 0) seg[idx] = info(0);
		else seg[idx] = info();
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, (idx << 1));
	build(mid + 1, r, (idx << 1) | 1);
	seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
}
void update(int pos, int val, int l = 0, int r = q, int idx = 1) {
	if (l == r) {
		if (val == 0) seg[idx] = info();
		else seg[idx] = info(val);
		return;
	}
	int mid = (l + r) >> 1;
	if (pos <= mid) update(pos, val, l, mid, (idx << 1));
	else update(pos, val, mid + 1, r, (idx << 1) | 1);
	seg[idx] = merge(seg[(idx << 1)], seg[(idx << 1) | 1]);
	// cerr << l << ' ' << r << ", " << idx << ": ";
	// cerr << seg[idx].net << ' ' << seg[idx].mini << ' ' << seg[idx].maxi << endl;
}
// range find net min/max
pii query1(int tl, int tr, int l = 0, int r = q, int idx = 1, int buff = 0) {
	if (tl > tr) return {0, 0};
	if (tl <= l && r <= tr) return {buff + seg[idx].mini, buff + seg[idx].maxi};
	int mid = (l + r) >> 1;
	pii res = {1e18, -1e18}, ret;
	if (tl <= mid) {
		ret = query1(tl, tr, l, mid, (idx << 1), buff);
		res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
	}
	if (tr > mid) {
		ret = query1(tl, tr, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
		res.ff = min(res.ff, ret.ff); res.ss = max(res.ss, ret.ss);
	}
	return res;
}
// find largest pos s.t. max(upd[pos..n]) - min(upd[pos..n]) > (tar = c[i])
int query2(int tar, pii range, int l = 0, int r = q, int idx = 1, int buff = 0) {
	// cerr << l << ' ' << r << ", " << idx << ": ";
	// cerr << seg[idx].net << ' ' << seg[idx].mini << ' ' << seg[idx].maxi << " | ";
	// cerr << range.ff << ' ' << range.ss << endl;
	if (max(range.ss, buff + seg[idx].maxi) - min(range.ff, buff + seg[idx].mini) <= tar) {
		return -1;
	}
	if (l == r) return l;
	int mid = (l + r) >> 1;
	int rmini = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].mini;
	int rmaxi = buff + seg[(idx << 1)].net + seg[(idx << 1) | 1].maxi;
	if (max(range.ss, rmaxi) - min(range.ff, rmini) <= tar) {
		range.ss = max(range.ss, rmaxi);
		range.ff = min(range.ff, rmini);
		return query2(tar, range, l, mid, (idx << 1), buff);
	} else {
		return query2(tar, range, mid + 1, r, (idx << 1) | 1, buff + seg[(idx << 1)].net);
	}
	return -1;
}

vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l,
                                   vector<int32_t> r, vector<int32_t> v) {
	
	n = c.size(); q = v.size();
	build();
	vector<pii> upd[n + 2];
	for (int i = 0; i < q; i++) {
		l[i]++; r[i]++;
		upd[l[i]].pb({i + 1, v[i]});
		upd[r[i] + 1].pb({i + 1, 0});
	}

	vector<int32_t> ans;
	for (int i = 1; i <= n; i++) {
		for (pii &cur : upd[i]) {
			update(cur.ff, cur.ss);
		}
		int tot = seg[1].net;
		int crit = query2(c[i - 1], {tot, tot});
		pii range;
		if (crit == -1) {
			range = query1(1, q);
			ans.pb(tot - range.ff);
			continue;
		}
		int prev = query1(crit, crit).ff;
		range = query1(crit + 1, q);
		// cerr << i << ": " << tot << ' ' << crit << ' ' << prev << " | ";
		// cerr << range.ff << ' ' << range.ss << endl;
		if (prev < range.ff) {
			range.ff = range.ss - c[i - 1];
			ans.pb(tot - range.ff);
		} else {
			range.ss = range.ff + c[i - 1];
			ans.pb(c[i - 1] - (range.ss - tot));
		}
	}
	return ans;
}

#undef int

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19072 KB Output is correct
2 Incorrect 8 ms 19028 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 19072 KB Output is correct
2 Incorrect 8 ms 19028 KB Output isn't correct
3 Halted 0 ms 0 KB -