제출 #438079

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
438079		Stickfish	사탕 분배 (IOI21_candies)	C++17	38 / 100	809 ms	19768 KiB

candies

#include "candies.h"
#include <vector>
#include <iostream>
#include <cassert>
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 isv_positive = true;
	for(int i = 0; i < q; ++i)
		isv_positive &= v[i] >= 0;
	if(isv_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 {
		stree tr;
		tr.init(n);
		for(int i = 0; i < q; ++i){
			tr.add(l[i], r[i], v[i]);
			//cout << "--- add " << l[i] << ' ' << r[i] << ' ' << v[i] << " ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
			tr.mineq(0, n, c[0]);
			//cout << "--- mineq ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
			tr.maxeq(0, n, 0);
			//cout << "--- maxeq ---\n";
			//for(int j = 0; j < n; ++j){
				//cout << tr.get(j) << ' ';
			//}
			//cout << '\n';
		}
		for(int i = 0; i < n; ++i){
			s[i] = tr.get(i);
		}
	}
    return s;
}

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