Submission #808153

#	Time	Username	Problem	Language	Result	Execution time	Memory
808153		khshg	Distributing Candies (IOI21_candies)	C++17	0 / 100	321 ms	19664 KiB

candies

#include <bits/stdc++.h>
using namespace std;
#define ll long long

// max -> x
// if mn <= mx < x ; add (x - mx)
// if x <= mn ; do nothing end
// assert(mn < x <= mx) go down

// min -> x
// if x < mn <= mx; add (x - mn)
// if mn <= mx <= x do nothing end
// assert(mn <= x < mx) go down

const int maxn = 200001;

struct node {
	int mn, mx;
	ll sum, lazy;
}st[4 * maxn];

#define tm ((tl + tr) >> 1)
#define lv ((v << 1) | 1)
#define rv (lv + 1)
void push(int v, int tl, int tr) {
	if(!st[v].lazy) return;
	st[lv].lazy += st[v].lazy;
	st[lv].sum += 1LL * (tm - tl + 1) * st[v].lazy;
	st[lv].mn += st[v].lazy;
	st[lv].mx += st[v].lazy;
	st[rv].lazy += st[v].lazy;
	st[rv].sum += 1LL * (tr - tm) * st[v].lazy;
	st[rv].mn += st[v].lazy;
	st[rv].mx += st[v].lazy;
	st[v].lazy = 0;
}

void pull(int v) {
	st[v].sum = st[lv].sum + st[rv].sum;
	st[v].mn = min(st[lv].mn, st[rv].mn);
	st[v].mx = max(st[lv].mx, st[rv].mx);
}

void add(int v, int tl, int tr, int l, int r, int val) {
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		st[v].lazy += val;
		st[v].sum += 1LL * (tr - tl + 1) * val;
		st[v].mn += val;
		st[v].mx += val;
		return;
	}
	push(v, tl, tr);
	add(lv, tl, tm, l, r, val);
	add(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void chmax(int v, int tl, int tr, int l, int r, int val) {
	if(tl > tr) return;
	if(tr < l || r < tl || st[v].mn >= val) return;
	if(l <= tl && tr <= r) {
		if(st[v].mx < val) {
			ll d = val - st[v].mx;
			st[v].lazy += d;
			st[v].sum += 1LL * (tr - tl + 1) * d;
			st[v].mn += d;
			st[v].mx += d;
		}
		if(val <= st[v].mn) return;
	}
	push(v, tl, tr);
	chmax(lv, tl, tm, l, r, val);
	chmax(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void chmin(int v, int tl, int tr, int l, int r, int val) {
	if(tl > tr) return;
	if(tr < l || r < tl || st[v].mx <= val) return;
	if(l <= tl && tr <= r) {
		if(val < st[v].mn) {
			ll d = val - st[v].mn;
			st[v].lazy += d;
			st[v].sum += 1LL * (tr - tl + 1) * d;
			st[v].mn += d;
			st[v].mx += d;
		}
		if(st[v].mx <= val) return;
	}
	push(v, tl, tr);
	chmin(lv, tl, tm, l, r, val);
	chmin(rv, tm + 1, tr, l, r, val);
	pull(v);
}

ll sum(int v, int tl, int tr, int l, int r) {
	if(tr < l || r < tl) return 0;
	if(l <= tl && tr <= r) return st[v].sum;
	push(v, tl, tr);
	return sum(lv, tl, tm, l, r) + sum(rv, tm + 1, tr, l, r);
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	int N = (int)C.size();
	int Q = (int)L.size();
	for(int i = 0; i < Q; ++i) {
		add(0, 0, N - 1, L[i], R[i], V[i]);
		chmin(0, 0, N - 1, 0, N - 1, C[0]);
		chmax(0, 0, N - 1, 0, N - 1, 0);
	}
	vector<int> ans(N);
	for(int i = 0; i < N; ++i) {
		ans[i] = sum(0, 0, N - 1, 0, 0);
	}
	return ans;
}

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