제출 #441578

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

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int MX = 200005;

struct segtree{
	int n;
	ll suffmn[MX * 2], suffmx[MX * 2], sm[MX * 2], vals[MX];

	segtree(int x) : n(x){
		memset(suffmn, 0, sizeof(suffmn));
		memset(suffmx, 0, sizeof(suffmx));
		memset(sm, 0, sizeof(sm));
		memset(vals, 0, sizeof(vals));
	}

	#define md (cl + cr) / 2
	#define lc nd + 1
	#define rc nd + 2 * (md - cl + 1)

	void update(int nd, int cl, int cr, int ps, ll val){
		if(ps < cl || cr < ps) return;
		if(cl == cr){
			suffmn[nd] = suffmx[nd] = sm[nd] = val;
			return;
		}

		update(lc, cl, md, ps, val);
		update(rc, md + 1, cr, ps, val);

		suffmn[nd] = min(suffmn[lc] + sm[rc], suffmn[rc]);
		suffmx[nd] = max(suffmx[lc] + sm[rc], suffmx[rc]);
		sm[nd] = sm[lc] + sm[rc];
	}

	void upd(int ps, ll val){
		vals[ps] = val;
		update(1, 0, n - 1, ps, val);
	}

	// smallest suff s.t. mx - mn > c
	pair<pair<ll, ll>, ll> query(int nd, int cl, int cr, ll sfmn, ll sfmx, ll sfsm, int c){
		if(cl == cr)
			return {{min(sfmn, sfsm + suffmn[nd]), max(sfmx, sfsm + suffmx[nd])}, cl};

		ll nwsfmn = min(sfmn, sfsm + suffmn[rc]);
		ll nwsfmx = max(sfmx, sfsm + suffmx[rc]);
		ll nwsfsm = sfsm + sm[rc];

		if(nwsfmx - nwsfmn > c)
			return query(rc, md + 1, cr, sfmn, sfmx, sfsm, c);
		return query(lc, cl, md, nwsfmn, nwsfmx, nwsfsm, c);
	}

	pair<pair<ll, ll>, ll> que(int c){
		return query(1, 0, n - 1, 0, 0, 0, c);
	}

	int tp(int x){
		return vals[x];
	}
};

vector<pair<int, int> > queriesL[MX], queriesR[MX];

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v){
	int n = c.size(), q = v.size();
	vector<int> ans(n);
	segtree st(q);

	for(int i = 0; i < q; i ++){
		queriesL[l[i]].push_back({i, v[i]});
		queriesR[r[i]].push_back({i, v[i]});
	}

	for(int i = 0; i < n; i ++){
		for(pair<int, int> j : queriesL[i])
			st.upd(j.first, -j.second);

		auto gt = st.que(c[i]);
		ll mn = gt.first.first, mx = gt.first.second, id = gt.second;
		if(mx - mn <= c[i] || st.tp(id) >= 0) ans[i] = -mn;
		else ans[i] = c[i] - mx;

		for(pair<int, int> j : queriesR[i])
			st.upd(j.first, 0);
	}

	return ans;
}

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