Submission #804605

#	Time	Username	Problem	Language	Result	Execution time	Memory
804605		ono_de206	Distributing Candies (IOI21_candies)	C++17	38 / 100	670 ms	54132 KiB

candies

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

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int mxn = 2e5 + 10;
const long long inf = 1e18 + 10;

// struct segTreeBeats {
// 	struct node {
// 		long long mx1, mx2, mn1, mn2, lz, mxc, mnc, sum;
// 		node(int x = 0) : mx1(x), mx2(-inf), mn1(x), mn2(inf), lz(0), mxc(1), mnc(1), sum(x) {}
// 		friend node operator+(const node &a, const node &b) {
// 			node ret;
// 			ret.sum = a.sum + b.sum;
// 			ret.mx1 = max(a.mx1, b.mx1);
// 			ret.mn1 = min(a.mn1, b.mn1);
// 			if(b.mx1 == a.mx1) {
// 				ret.mxc = a.mxc + b.mxc;
// 				ret.mx2 = max(a.mx2, b.mx2);
// 			} else {
// 				if(b.mx1 > a.mx1) {
// 					ret.mxc = b.mxc;
// 					ret.mx2 = max(a.mx1, b.mx2);
// 				} else {
// 					ret.mxc = a.mxc;
// 					ret.mx2 = max(a.mx2, b.mx1);
// 				}
// 			}

// 			if(b.mn1 == a.mn1) {
// 				ret.mnc = a.mnc + b.mnc;
// 				ret.mn2 = min(a.mn2, b.mn2);
// 			} else {
// 				if(b.mn1 < a.mn1) {
// 					ret.mnc = b.mnc;
// 					ret.mn2 = min(a.mn1, b.mn2);
// 				} else {
// 					ret.mnc = a.mnc;
// 					ret.mn2 = min(a.mn2, b.mn1);
// 				}
// 			}
// 			return ret;
// 		}
// 	};
// 	vector<node> d;
// 	vector<int> c;
// 	int n;

// 	void build(int l, int r, int i) {
// 		if(l == r) {
// 			d[i] = c[l];
// 			return;
// 		}
// 		int m = (l + r) / 2;
// 		build(l, m, i * 2);
// 		build(m + 1, r, i * 2 + 1);
// 		d[i] = d[i * 2] + d[i * 2 + 1];
// 	}

// 	segTreeBeats(int _n, vector<int> _c) {
// 		n = _n;
// 		c = _c;
// 		d.resize(n * 4 + 10);
// 		build(0, n - 1, 1);
// 	}

// 	void ADD(int i, int l, int r, long long v) {
// 		d[i].sum += 1LL * v * (r - l + 1);
// 		d[i].mx1 += v; d[i].mn1 += v; 
// 		if(d[i].mx2 != -inf) d[i].mx2 += v;
// 		if(d[i].mn2 != inf) d[i].mn2 += v;
// 		d[i].lz += v;
// 	}

// 	void MNN(int i, int l, int r, long long v) {
// 		if(v >= d[i].mx1) return;
// 		d[i].sum -= d[i].mxc * d[i].mx1;
// 		d[i].mx1 = v;
// 		d[i].sum += d[i].mxc * d[i].mx1;
// 		if(l == r) d[i].mn1 = d[i].mx1;
// 		else { 
// 			if(d[i].mn1 >= v) d[i].mn1 = v;
// 			else if(d[i].mn2 > v) d[i].mn2 = v;
// 		}
// 	}

// 	void MXX(int i, int l, int r, long long v) {
// 		if(v <= d[i].mn1) return;
// 		d[i].sum -= d[i].mnc * d[i].mn1;
// 		d[i].mn1 = v;
// 		d[i].sum += d[i].mnc * d[i].mn1;
// 		if(l == r) d[i].mx1 = d[i].mn1;
// 		else { 
// 			if(d[i].mx1 <= v) d[i].mx1 = v;
// 			else if(d[i].mn2 < v) d[i].mx2 = v;
// 		}
// 	}

// 	void pro(int i, int l, int r) {
// 		if(l == r) return;
// 		int m = (l + r) / 2;
// 		ADD(i * 2, l, m, d[i].lz);
// 		ADD(i * 2 + 1, m + 1, r, d[i].lz);
// 		d[i].lz = 0;

// 		MNN(i * 2, l, m, d[i].mx1);
// 		MNN(i * 2 + 1, m + 1, r, d[i].mx1);

// 		MXX(i * 2, l, m, d[i].mn1);
// 		MXX(i * 2 + 1, m + 1, r, d[i].mn1);
// 	}

// 	void Add(int l, int r, int i, int x, int y, long long v) {
// 		if(l > y || r < x) return;
// 		if(l >= x && r <= y) {
// 			ADD(i, l, r, v);
// 			return;
// 		}
// 		pro(i, l, r);
// 		int m = (l + r) / 2;
// 		Add(l, m, i * 2, x, y, v);
// 		Add(m + 1, r, i * 2 + 1, x, y, v);
// 		d[i] = d[i * 2] + d[i * 2 + 1];
// 	}

// 	void Mnn(int l, int r, int i, int x, int y, long long v) {
// 		if(l > y || r < x || d[i].mx1 <= v) return;
// 		if(l >= x && r <= y && d[i].mx2 < v) {
// 			MNN(i, l, r, v);
// 			return;
// 		}
// 		pro(i, l, r);
// 		int m = (l + r) / 2;
// 		Mnn(l, m, i * 2, x, y, v);
// 		Mnn(m + 1, r, i * 2 + 1, x, y, v);
// 		d[i] = d[i * 2] + d[i * 2 + 1];
// 	}

// 	void Mxx(int l, int r, int i, int x, int y, long long v) {
// 		if(l > y || r < x || d[i].mn1 >= v) return;
// 		if(l >= x && r <= y && d[i].mn2 > v) {
// 			MXX(i, l, r, v);
// 			return;
// 		}
// 		pro(i, l, r);
// 		int m = (l + r) / 2;
// 		Mxx(l, m, i * 2, x, y, v);
// 		Mxx(m + 1, r, i * 2 + 1, x, y, v);
// 		d[i] = d[i * 2] + d[i * 2 + 1];
// 	}

// 	void add(int l, int r, long long v) {
// 		Add(0, n - 1, 1, l, r, v);
// 	}

// 	void mnn(int l, int r, long long v) {
// 		Mnn(0, n - 1, 1, l, r, v);
// 	}

// 	void mxx(int l, int r, long long v) {
// 		Mxx(0, n - 1, 1, l, r, v);
// 	}

// 	long long GetSum(int l, int r, int i, int x, int y) {
// 		if(l >= x && r <= y) return d[i].sum;
// 		if(l > y || r < x) return 0LL;
// 		pro(i, l, r);
// 		int m = (l + r) / 2;
// 		return GetSum(l, m, i * 2, x, y) + GetSum(m + 1, r, i * 2 + 1, x, y);
// 	}

// 	long long getSum(int l, int r) {
// 		return GetSum(0, n - 1, 1, l, r);
// 	}
// };
struct segTreeBeat {
	int l, r, m;
	long long sum, max1, max2, min1, min2, maxc, minc, lz;
	segTreeBeat *le, *ri;

	void up() {
		assert(le != NULL);
		assert(ri != NULL);
		sum = le->sum + ri->sum;

		max1 = max(le->max1, ri->max1);
		min1 = min(le->min1, ri->min1);

		max2 = -inf;
		min2 = inf;

		if(le->max1 == ri->max1) {
			maxc = le->maxc + ri->maxc;
			max2 = max(le->max2, ri->max2);
		} else {
			if(le->max1 > ri->max1) {
				maxc = le->maxc;
				max2 = max(le->max2, ri->max1);
			} else {
				maxc = ri->maxc;
				max2 = max(le->max1, ri->max2);
			}
		}

		if(le->min1 == ri->min1) {
			minc = le->minc + ri->minc;
			min2 = min(le->min2, ri->min2);
		} else {
			if(le->min1 < ri->min1) {
				minc = le->minc;
				min2 = min(le->min2, ri->min1);
			} else {
				minc = ri->minc;
				min2 = min(le->min1, ri->min2);
			}
		}
	}

	segTreeBeat(int _l, int _r, vector<int> &a) {
		l = _l; r = _r; m = (l + r) / 2;
		lz = 0;
		if(l == r) {
			sum = max1 = min1 = a[l];
			maxc = minc = 1;
			max2 = -inf; min2 = inf;
			le = ri = NULL;
			return;
		}
		le = new segTreeBeat(l, m, a);
		ri = new segTreeBeat(m + 1, r, a);
		up();
	}

	void proAdd(long long x) {
		sum += x * (r - l + 1);
		max1 += x; min1 += x;
		if(max2 != -inf) max2 += x;
		if(min2 != inf) min2 += x;
		lz += x;
	}

	void proMax(long long x) {
		if(x >= max1) return;
		sum -= maxc * max1;
		max1 = x;
		sum += maxc * max1;

		if(l == r) {
			min1 = x;
		} else {
			if(x <= min1) min1 = x;
			else if(x < min2) min2 = x;
		}
	}

	void proMin(long long x) {
		if(x <= min1) return;
		sum -= minc * min1;
		min1 = x;
		sum += minc * min1;

		if(l == r) {
			max1 = x;
		} else {
			if(x >= max1) max1 = x;
			else if(x > max2) max2 = x;
		}
	}

	void pro() {
		if(l == r) return;
		// if(le == NULL) le = new segTreeBeat(l, m);
		// if(ri == NULL) ri = new segTreeBeat(m + 1, r);

		le->proAdd(lz);
		ri->proAdd(lz);
		lz = 0;

		le->proMax(max1);
		ri->proMax(max1);

		le->proMin(min1);
		ri->proMin(min1);
	}

	void add(int x, int y, long long v) {
		if(l > y || r < x) return;
		if(l >= x && r <= y) {
			proAdd(v);
			return;
		} 
		pro();
		le->add(x, y, v);
		ri->add(x, y, v);
		up();
	}

	void mnn(int x, int y, long long v) {
		if(l > y || r < x || max1 <= v) return;
		if(l >= x && r <= y && max2 < v) {
			proMax(v);
			return;
		}
		pro();
		le->mnn(x, y, v);
		ri->mnn(x, y, v);
		up();
	}
	void mxx(int x, int y, long long v) {
		if(l > y || r < x || min1 >= v) return;
		if(l >= x && r <= y && min2 > v) {
			proMin(v);
			return;
		}
		pro();
		le->mxx(x, y, v);
		ri->mxx(x, y, v);
		up();
	}
	long long getSum(int x, int y) {
		if(l > y || r < x) return 0LL;
		if(l >= x && r <= y) return sum;
		pro();
		return le->getSum(x, y) + ri->getSum(x, y);
	}
	long long getMax(int x, int y) {
		if(l > y || r < x) return -inf;
		if(l >= x && r <= y) return max1;
		pro();
		return max(le->getMax(x, y), ri->getMax(x, y));
	}
	long long getMin(int x, int y) {
		if(l > y || r < x) return inf;
		if(l >= x && r <= y) return min1;
		pro();
		return max(le->getMin(x, y), ri->getMin(x, y));
	}
	~segTreeBeat() {
		if(le != NULL) delete le;
		if(ri != NULL) delete ri;
	}
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
	int n = c.size(), q = l.size();
	vector<long long> ret(n);
	if(n * q <= 2000 * 2000) {
		for(int i = 0; i < q; i++) {
			for(int j = l[i]; j <= r[i]; j++) {
				ret[j] += v[i];
				ret[j] = min(1ll * c[j], max(0ll, ret[j]));
			}
		}
		return vector<int>(all(ret));
	}
	if(*min_element(all(v)) >= 0) {
		for(int i = 0; i < q; i++) {
			ret[l[i]] += v[i];
			if(r[i] + 1 < n) ret[r[i] + 1] -= v[i];
		}
		for(int i = 1; i < n; i++) {
			ret[i] += ret[i - 1];
		}
		for(int i = 0; i < n; i++) {
			ret[i] = min(1ll * c[i], max(0ll, ret[i]));
		}
		return vector<int>(all(ret));
	}
	if(*max_element(all(c)) == *min_element(all(c))) {
		vector<int> tmp(n, 0);
		segTreeBeat *st = new segTreeBeat(0, n - 1, tmp);
		for(int i = 0; i < q; i++) {
			st->add(l[i], r[i], v[i]);
			st->mnn(l[i], r[i], c[0]);
			st->mxx(l[i], r[i], 0);
		}
		for(int i = 0; i < n; i++) {
			ret[i] = st->getSum(i, i);
		}
		return vector<int>(all(ret));
	}
	exit(1);
	return vector<int>(all(ret));
}

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