Submission #438195

#	Time	Username	Problem	Language	Result	Execution time	Memory
438195		Stickfish	Distributing Candies (IOI21_candies)	C++17	64 / 100	980 ms	23752 KiB

candies

#include "candies.h"
#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
using ll = long long;

const int MAXN = 2e5 + 123;
const ll INF = 1e18 + 177013;

struct upd{
	ll add;
	pair<ll, ll> sg;

	upd(): add(0), sg(0, INF) {}

	upd(ll add_, ll mineq_, ll maxeq_): add(add_), sg(maxeq_, mineq_){}
};

ll into_seg(ll x, pair<ll, ll> sg){
	if(x < sg.first)
		return sg.first;
	if(x > sg.second)
		return sg.second;
	return x;
}

pair<ll, ll> cover(pair<ll, ll> oldsg, pair<ll, ll> newsg){
	return {into_seg(oldsg.first, newsg), into_seg(oldsg.second, newsg)};
}

struct stree{
	void init(int n){
		sz = 1;
		while(sz < n)
			sz *= 2;
		mod.assign(sz * 2 - 1, upd());
	}

	void add(int l, int r, ll vl){
		add(0, 0, sz, l, r, vl);
	}

	void mineq(int l, int r, ll vl){
		mineq(0, 0, sz, l, r, vl);
	}

	void maxeq(int l, int r, ll vl){
		maxeq(0, 0, sz, l, r, vl);
	}

	ll get(int i){
		return get(0, 0, sz, i);
	}
private:
	int sz;
	vector<upd> mod;

	void push(int ind){
		if(ind * 2 + 1 >= sz * 2 - 1)
			return;
		mod[ind * 2 + 1].add += mod[ind].add;
		mod[ind * 2 + 1].sg.first += mod[ind].add;
		mod[ind * 2 + 1].sg.second += mod[ind].add;
		mod[ind * 2 + 1].sg = cover(mod[ind * 2 + 1].sg, mod[ind].sg);
		
		mod[ind * 2 + 2].add += mod[ind].add;
		mod[ind * 2 + 2].sg.first += mod[ind].add;
		mod[ind * 2 + 2].sg.second += mod[ind].add;
		mod[ind * 2 + 2].sg = cover(mod[ind * 2 + 2].sg, mod[ind].sg);

		mod[ind] = upd();
	}

	void add(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].add += vl;
			mod[ind].sg.first += vl;
			mod[ind].sg.second += vl;
			return;
		}
		int mnd = (lnd + rnd) / 2;
		add(ind * 2 + 1, lnd, mnd, l, r, vl);
		add(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	void mineq(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].sg = cover(mod[ind].sg, {-INF, vl});
			return;
		}
		int mnd = (lnd + rnd) / 2;
		mineq(ind * 2 + 1, lnd, mnd, l, r, vl);
		mineq(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	void maxeq(int ind, int lnd, int rnd, int l, int r, ll vl){
		push(ind);
		if(lnd >= r || rnd <= l)
			return;
		if(lnd >= l && rnd <= r){
			mod[ind].sg = cover(mod[ind].sg, {vl, INF});
			return;
		}
		int mnd = (lnd + rnd) / 2;
		maxeq(ind * 2 + 1, lnd, mnd, l, r, vl);
		maxeq(ind * 2 + 2, mnd, rnd, l, r, vl);
	}

	ll get(int ind, int lnd, int rnd, int i){
		push(ind);
		if(rnd - lnd == 1){
			return into_seg(mod[ind].add, mod[ind].sg);
		}
		int mnd = (lnd + rnd) / 2;
		if(i < mnd)
			return get(ind * 2 + 1, lnd, mnd, i);
		return get(ind * 2 + 2, mnd, rnd, i);
	}
};


vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
	int q = l.size();
    vector<int> s(n, 0);
	for(int i = 0; i < q; ++i)
		++r[i];
	
	//if(n <= 2000){
		//for(int qi = 0; qi < q; ++qi){
			//for(int i = l[qi]; i < r[qi]; ++i){
				//s[i] += v[qi];
				//s[i] = max(s[i], 0);
				//s[i] = min(s[i], c[i]);
			//}
		//}
		//return s;
	//}

	bool is_v_positive = true;
	bool is_c_same = true;
	for(int i = 0; i < q; ++i)
		is_v_positive &= v[i] >= 0;
	for(int i = 1; i < n; ++i)
		is_c_same &= c[i] == c[0];
	if(is_v_positive){
		vector<ll> pf(n + 1, 0);
		for(int qi = 0; qi < q; ++qi){
			pf[l[qi]] += v[qi];
			pf[r[qi]] -= v[qi];
		}
		ll sm = 0;
		for(int i = 0; i < n; ++i){
			sm += pf[i];
			s[i] = int(min(sm, 1ll * c[i]));
		}
		return s;
	} else if(is_c_same){
		stree tr;
		tr.init(n);
		for(int i = 0; i < q; ++i){
			tr.add(l[i], r[i], v[i]);
			tr.mineq(0, n, c[0]);
			tr.maxeq(0, n, 0);
		}
		for(int i = 0; i < n; ++i){
			s[i] = tr.get(i);
		}
	} else {
		vector<pair<int, int>> dcr;
		for(int i = 0; i < n; ++i)
			dcr.push_back({c[i], i});
		sort(dcr.rbegin(), dcr.rend());
		ll border = INF;
		ll borderpos = 0;
		ll lastvl = 0;
		bool borderzero = true;
		for(auto [ci, i] : dcr){
			if(ci >= border){
				s[i] = lastvl;
			} else {
				ll vl = ci;
				if(borderzero)
					vl = 0;
				for(int j = borderpos; j < q; ++j){
					vl += v[j];
					if(vl <= 0){
						vl = 0;
						border = 0;
						borderpos = j + 1;
						borderzero = true;
					} else if(vl >= ci){
						vl = ci;
					}
					if(vl >= border){
						border = vl;
						borderpos = j + 1;
						borderzero = false;
					}
				}
				lastvl = vl;
			}
			s[i] = lastvl;
		}
	}
    return s;
}

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