제출 #448551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
448551		grt	사탕 분배 (IOI21_candies)	C++17	100 / 100	642 ms	36640 KiB

candies

#include <bits/stdc++.h>
#define ST first
#define ND second
#define PB push_back

using namespace std;
using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200 * 1000 + 10;
const ll INF = 1e18;
int n, q;

struct Node {
	ll g, mi, mx;
};

Node T[(1 << 19)];
vi events[nax];

void prop(int v) {
	T[2*v].g += T[v].g;
	T[2*v + 1].g += T[v].g;
	T[v].g = 0;
}

void add(int a, int b, int l, int r, int x, int v) {
	if(a <= l && r <= b) {
		T[v].g += x;
		return;
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) add(a, b, l, mid, x, v * 2);
	if(mid < b) add(a, b, mid + 1, r, x, v * 2 + 1);
	T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
	T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
}

tuple<int,ll,ll> ask(int d) {
	int v = 1, l = 0, r = q - 1;
	ll mi = INF, mx = -INF;
	while(l < r) {
		T[v].mi += T[v].g;
		T[v].mx += T[v].g;
		prop(v);
		//cout << l << " " << r << "\n";
		int mid = (l + r) / 2;
		if(max(mx, T[2 * v + 1].mx + T[2*v+1].g) - min(mi, T[2 * v + 1].mi + T[2*v + 1].g) > d) {
			v = v * 2 + 1;
			l = mid + 1;
		} else {
			mx = max(mx, T[2 * v + 1].mx + T[2*v + 1].g);
			mi = min(mi, T[2 * v + 1].mi + T[2*v + 1].g);
			v = v * 2;
			r = mid;
		}
	}
	mi = min(mi, T[v].g + T[v].mi);
	mx = max(mx, T[v].g + T[v].mx);
	return {l, mi, mx};
}

pair<ll,ll>qr(int a, int b, int l, int r, int v) {
	if(a <= l && r <= b) {
		return {T[v].mi + T[v].g, T[v].mx + T[v].g};
	}
	int mid = (l + r) / 2;
	prop(v);
	pair<ll,ll>w = {INF, -INF};
	if(a <= mid) {
		auto y = qr(a, b, l, mid, v * 2);
		w = {min(w.ST, y.ST), max(w.ND, y.ND)};
	}
	if(mid < b) {
		auto y = qr(a, b, mid + 1, r, v * 2 + 1);
		w = {min(w.ST, y.ST), max(w.ND, y.ND)};
	}
	T[v].mi = min(T[2*v].mi + T[2*v].g, T[2*v+1].mi + T[2*v+1].g);
	T[v].mx = max(T[2*v].mx + T[2*v].g, T[2*v+1].mx + T[2*v+1].g);
	return w;
}




vi distribute_candies(vi c, vi la, vi ra, vi v) {
	n = (int)c.size();
	q = (int)la.size();
	for(int i = 0; i < q; ++i) {
		events[la[i]].PB(i + 1);
		events[ra[i] + 1].PB(-i - 1);
	}
	q++;
	vi ans(n);
	for(int i = 0; i < n; ++i) {
		for(int x : events[i]) {
			if(x > 0) {
				add(x, q - 1, 0, q - 1, v[x - 1], 1);
			} else {
				x = -x;
				add(x, q - 1, 0, q - 1, -v[x - 1], 1);
			}
		}
		auto [pos, mi, mx] = ask(c[i]);
		//cout << pos << " " << mi << " " << mx << "\n";
		auto zz = qr(q - 1, q - 1, 0, q - 1, 1);
		if(mx - mi <= c[i]) {
			auto z2 = qr(0, q - 1, 0, q - 1, 1);
			ans[i] = zz.ST - z2.ST;
		} else {
			auto z = qr(pos + 1, q - 1, 0, q - 1, 1);
			if(mi < z.ST) {
				ans[i] = c[i] - (z.ND - zz.ST);
			} else {
				ans[i] = zz.ST - z.ST;
			}
		}
		
	}
	return ans;
}

//int main() {
	//ios_base::sync_with_stdio(0);
	//cin.tie(0);
	//int N, Q;
	//cin >> N >> Q;
	//vi c(N), l(Q), r(Q), v(Q);
	//for(int i = 0; i < N; ++i) {
		//cin >> c[i];
	//}
	//for(int i = 0; i < Q; ++i) {
		//cin >> l[i] >> r[i] >> v[i];
	//}
	//auto ans = distribute_candies(c,l,r,v);
	//for(int x : ans) cout << x << " ";
//}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33