Submission #483889

#	Time	Username	Problem	Language	Result	Execution time	Memory
483889		8e7	사탕 분배 (IOI21_candies)	C++17	100 / 100	617 ms	45668 KiB

candies

//Challenge: Accepted
#include "candies.h"
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ...b) {
	cout << a << " ", debug(b ...);
};
template<class T> void pary (T l, T r) {
	while (l!= r) cout << *l << " ", l++;
	cout << endl;
};
#define ll long long
#define maxn 200005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const ll inf = 1LL<<60;
struct segtree{
	ll ma[4 * maxn], mi[4 * maxn], tag[4 * maxn];	
	int ama[4 * maxn], ami[4 * maxn];
	void init(int cur, int l, int r) {
		if (r <= l) return;
		if (r - l == 1) {
			ama[cur] = ami[cur] = l;
			return;
		}
		int mid = (l + r) / 2;
		init(cur * 2, l, mid), init(cur * 2 + 1, mid, r);
		ama[cur] = ami[cur] = l;
	}
	void push(int cur, int l, int r) {
		if (!tag[cur]) return;
		ma[cur] += tag[cur], mi[cur] += tag[cur];
		if (r - l > 1) tag[cur * 2] += tag[cur], tag[cur * 2 + 1] += tag[cur];
		tag[cur] = 0;		
	}
	void pull(int cur, int l, int r) {
		push(cur, l, r);
		if (r - l < 2) return;
		int m = (l + r) / 2;
		push(cur * 2, l, m), push(cur * 2 + 1, m, r);	
		if (ma[cur*2] > ma[cur*2+1]) ma[cur] = ma[cur*2], ama[cur] = ama[cur*2];
		else ma[cur] = ma[cur*2+1], ama[cur] = ama[cur*2+1];
		if (mi[cur*2] < mi[cur*2+1]) mi[cur] = mi[cur*2], ami[cur] = ami[cur*2];
		else mi[cur] = mi[cur*2+1], ami[cur] = ami[cur*2+1];
	}
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || ql >= r || qr <= l) return;
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			tag[cur] += val;return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val), modify(cur*2+1, mid, r, ql, qr, val);
		pull(cur, l, r);
		//debug("seg", l, r, ma[cur], mi[cur]);
	}
	pii search(int cur, int l, int r,ll big, ll small,ll c) { //maximum id 
		push(cur, l, r);
		if (max(big, ma[cur]) - min(small, mi[cur]) <= c) {
			//debug("f", max(big, ma[cur]), min(small, mi[cur]), c, l, r);
			return make_pair(-1, 0);
		}
		if (r - l == 1) {
			return {l, (ma[cur] - small > c ? 0 : c)};
		}
		int m = (l + r) / 2;
		pull(cur, l, r);
		if (max(ma[cur*2+1], big) - min(small, mi[cur*2+1]) > c) {
			//debug("rig", m, r);
			return search(cur*2+1, m, r, big, small, c);
		} else {
			return search(cur*2, l, m, max(ma[cur*2+1], big), min(small, mi[cur*2+1]), c);
		}
	}
	pii getval(int cur, int l, int r, int ql, int qr) { //returns max, min of segment
		if (r <= l || ql >= r || qr <= l) return {-inf, inf};
		push(cur, l, r);
		if (ql <= l && qr >= r) {
			pull(cur, l, r);
			return {ma[cur], mi[cur]};
		}
		int m = (l + r) / 2;
		pii lef = getval(cur * 2, l, m, ql, qr), rig = getval(cur*2+1, m, r, ql, qr);
		return make_pair(max(lef.ff, rig.ff), min(lef.ss, rig.ss));
	}
}seg;
vector<pii> ch[maxn];
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> ret(n, 0);
	for (int i = 0;i < q;i++) {
		ch[l[i]].push_back({v[i], i+1});
		ch[r[i] + 1].push_back({-v[i], i+1});
	}
	q++;
	seg.init(1, 0, q);	
	for (int i = 0;i < n;i++) {
		for (auto p:ch[i]) {
			//debug("mod", p.ss, q, p.ff);
			seg.modify(1, 0, q, p.ss, q, p.ff);	
		}
		pii p = seg.search(1, 0, q, -inf, inf, c[i]), last = seg.getval(1, 0, q, q-1, q);
		//debug(p.ff, p.ss);
		if (p.ff == -1) {
			pii all = seg.getval(1, 0, q, 0, q);
			ret[i] = last.ff - all.ss;
			//debug(0, last.ff, all.ss);
		} else {
			pii rem = seg.getval(1, 0, q, p.ff+1, q);
			if (p.ss == 0) ret[i] = last.ff - rem.ss;
			else ret[i] = c[i] - (rem.ff - last.ff);
			//debug(1, last.ff, rem.ff, rem.ss, p.ss);
		}
		//debug(i, ret[i]);
	}
	return ret;
}
/*
6
2 12 11 7 1 19
4
4 5 14
0 4 14
1 4 10
5 5 -18
*/

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