Submission #806108

#	Time	Username	Problem	Language	Result	Execution time	Memory
806108		ono_de206	Distributing Candies (IOI21_candies)	C++17	0 / 100	145 ms	23964 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 {
	int l, r, m;
	long long sum, max1, max2, min1, min2, maxc, minc, lz;
	segTreeBeats *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);
			}
		}
	}

	segTreeBeats(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 segTreeBeats(l, m, a);
		ri = new segTreeBeats(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));
	}
	~segTreeBeats() {
		if(le != NULL) delete le;
		if(ri != NULL) delete ri;
	}
};

int a[mxn];

struct seg {
	int mx, mn, resmx, resmn, lz, zero, ismax;
} d[mxn * 4];

void up(int i) {
	d[i].mx = d[i * 2 + 1].mx;
	d[i].resmx = d[i * 2 + 1].resmx;
	d[i].mn = d[i * 2].mn;
	d[i].resmn = d[i * 2].resmn;
}

void pro(int i, int l, int r) {
	if(d[i].zero) {
		d[i].mx = d[i].mn = 0;
		d[i].resmx = a[r];
		d[i].resmn = a[l];
		d[i].lz = d[i].ismax = 0;

		if(l < r) {
			d[i * 2].zero = 1;
			d[i * 2 + 1].zero = 1;
			d[i * 2].ismax = d[i * 2].lz = 0;
			d[i * 2 + 1].ismax = d[i * 2 + 1].lz = 0;
		}
	}

	if(d[i].ismax) {
		d[i].mx = a[r]; 
		d[i].mn = a[l];
		d[i].resmx = d[i].resmn = 0;
		d[i].lz = d[i].zero = 0;

		if(l < r) {
			d[i * 2].ismax = 1;
			d[i * 2 + 1].ismax = 1;
			d[i * 2].zero = d[i * 2].lz = 0;
			d[i * 2 + 1].zero = d[i * 2 + 1].lz = 0;
		}
	}

	if(d[i].lz != 0) {
		d[i].mx += d[i].lz;
		d[i].mn += d[i].lz;
		d[i].resmx -= d[i].lz;
		d[i].resmn -= d[i].lz;

		if(l < r) {
			d[i * 2].lz += d[i].lz;
			d[i * 2 + 1].lz += d[i].lz;
		}
	}

	d[i].lz = d[i].zero = d[i].ismax = 0;
}

void build(int l, int r, int i) {
	d[i].lz = d[i].zero = d[i].ismax = 0;
	if(l == r) {
		d[i].mx = d[i].mn = 0;
		d[i].resmx = d[i].resmn = a[l];
		return;
	}
	int m = (l + r) / 2;
	build(l, m, i * 2);
	build(m + 1, r, i * 2 + 1);
	up(i);
}

void setZero(int l, int r, int i, int x, int y) {
	pro(i, l, r);
	if(x > y) return;
	if(l > y || r < x) return;
	if(l >= x && r <= y) {
		d[i].zero = 1;
		pro(i, l, r);
		return;
	}
	int m = (l + r) / 2;
	setZero(l, m, i * 2, x, y);
	setZero(m + 1, r, i * 2 + 1, x, y);
	up(i);
}

void setMax(int l, int r, int i, int x, int y) {
	pro(i, l, r);
	if(x > y) return;
	if(l > y || r < x) return;
	if(l >= x && r <= y) {
		d[i].ismax = 1;
		pro(i, l, r);
		return;
	}
	int m = (l + r) / 2;
	setMax(l, m, i * 2, x, y);
	setMax(m + 1, r, i * 2 + 1, x, y);
	up(i);
}

void add(int l, int r, int i, int x, int y, int val) {
	pro(i, l, r);
	if(x > y) return;
	if(l > y || r < x) return;
	if(l >= x && r <= y) {
		d[i].lz += val;
		pro(i, l, r);
		return;
	}
	int m = (l + r) / 2;
	add(l, m, i * 2, x, y, val);
	add(m + 1, r, i * 2 + 1, x, y, val);
	up(i);
}

int getLeftMax(int l, int r, int i, int val) {
	pro(i, l, r);
	if(d[i].mx < val) return -1;
	if(l == r) return l;
	int m = (l + r) / 2;
	int ret = getLeftMax(l, m, i * 2, val);
	if(ret == -1) ret = getLeftMax(m + 1, r, i * 2 + 1, val);
	return ret;
}

int getLeftResmax(int l, int r, int i, int val) {
	pro(i, l, r);
	if(d[i].resmx < val) return -1;
	if(l == r) return l;
	int m = (l + r) / 2;
	int ret = getLeftResmax(l, m, i * 2, val);
	if(ret == -1) ret = getLeftResmax(m + 1, r, i * 2 + 1, val);
	return ret;
}

int get(int l, int r, int i, int x) {
	pro(i, l, r);
	if(l == r) return d[i].mx;
	int m = (l + r) / 2;
	if(x <= m) return get(l, m, i * 2, x);
	return get(m + 1, r, i * 2 + 1, x);
}

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);
	// 	segTreeBeats *st = new segTreeBeats(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));
	// }
	}
	sort(all(c));
	for(int i = 1; i <= n; i++) {
		a[i] = c[i  - 1];
	}
	build(1, n, 1);
	for(int j = 0; j < q; j++) {
		if(v[j] == 0) continue;
		if(v[j] < 0) {
			int p = getLeftMax(1, n, 1, -v[j]);
			if(p == -1) p = n + 1;
			setZero(1, n, 1, 1, p - 1);
			add(1, n, 1, p, n, v[j]);
		} else {
			int p = getLeftResmax(1, n, 1, v[j]);
			if(p == -1) p = n + 1;
			setMax(1, n, 1, 1, p - 1);
			add(1, n, 1, p, n, v[j]);
		}
	}
	for(int i = 0; i < n; i++) {
		ret[i] = get(1, n, 1, i + 1);
	}
	return vector<int>(all(ret));
}

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