Submission #804610

#	Time	Username	Problem	Language	Result	Execution time	Memory
804610		khshg	Distributing Candies (IOI21_candies)	C++17	0 / 100	524 ms	40576 KiB

candies

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

const int maxn = 2e5 + 1;
const long long INF = 1e18;

struct node {
	long long sum;
	long long lazy;
	long long mncnt, mxcnt, mn0, mn1, mx0, mx1;
} st[4 * maxn];

#define tm ((tl + tr) >> 1)
#define lv ((v << 1) | 1)
#define rv (lv + 1)
void pull(int v) {
	st[v].sum = st[lv].sum + st[rv].sum;
	if(st[lv].mn0 == st[rv].mn0) {
		st[v].mn0 = st[lv].mn0;
		st[v].mncnt = st[lv].mncnt + st[rv].mncnt;
		st[v].mn1 = min(st[lv].mn1, st[rv].mn1);
	} else if(st[lv].mn0 < st[rv].mn0) {
		st[v].mn0 = st[lv].mn0;
		st[v].mncnt = st[lv].mncnt;
		st[v].mn1 = min(st[lv].mn1, st[rv].mn0);
	} else {
		st[v].mn0 = st[rv].mn0;
		st[v].mncnt = st[rv].mncnt;
		st[v].mn1 = min(st[rv].mn1, st[lv].mn0);
	}
	if(st[lv].mx0 == st[rv].mx0) {
		st[v].mx0 = st[lv].mx0;
		st[v].mxcnt = st[lv].mxcnt + st[rv].mxcnt;
		st[v].mx1 = max(st[lv].mx1, st[rv].mx1);
	} else if(st[lv].mx0 > st[rv].mx0) {
		st[v].mx0 = st[lv].mx0;
		st[v].mxcnt = st[lv].mxcnt;
		st[v].mx1 = max(st[lv].mx1, st[rv].mx0);
	} else {
		st[v].mx0 = st[rv].mx0;
		st[v].mxcnt = st[rv].mxcnt;
		st[v].mx1 = min(st[rv].mx1, st[lv].mx0);
	}
}
void push_lazy(int v, int tl, int tr) {
	if(!st[v].lazy) return;
	st[lv].sum += st[v].lazy * (tm - tl + 1);
	st[lv].mn0 += st[v].lazy;
	st[lv].mn1 += st[v].lazy;
	st[lv].mx0 += st[v].lazy;
	st[lv].mx1 += st[v].lazy;
	st[lv].lazy += st[v].lazy;
	st[rv].sum += st[v].lazy * (tr - (tm + 1) + 1);
	st[rv].mn0 += st[v].lazy;
	st[rv].mn1 += st[v].lazy;
	st[rv].mx0 += st[v].lazy;
	st[rv].mx1 += st[v].lazy;
	st[rv].lazy += st[v].lazy;
	st[v].lazy = 0LL;
}
void push_range(int v) {
	if(st[lv].mn0 < st[v].mn0) {
		st[lv].sum -= st[lv].mncnt * (st[v].mn0 - st[lv].mn0);
		st[lv].mn0 = st[v].mn0;
	}
	if(st[rv].mn0 < st[v].mn0) {
		st[rv].sum -= st[rv].mncnt * (st[v].mn0 - st[rv].mn0);
		st[rv].mn0 = st[v].mn0;
	}
	if(st[lv].mx0 > st[v].mx0) {
		st[lv].sum -= st[lv].mxcnt * (st[lv].mx0 - st[v].mx0);
		st[lv].mx0 = st[v].mx0;
	}
	if(st[rv].mx0 > st[v].mx0) {
		st[rv].sum -= st[rv].mxcnt * (st[rv].mx0 - st[v].mx0);
		st[rv].mx0 = st[v].mx0;
	}
}

void st_add(int v, int tl, int tr, int l, int r, ll val) {
	if(tr < l || tl > r) return;
	if(l <= tl && tr <= r) {
		st[v].sum += val * (tr - tl + 1);
		st[v].mn0 += val;
		st[v].mn1 += val;
		st[v].mx0 += val;
		st[v].mx1 += val;
		st[v].lazy += val;
		return;
	}
	push_lazy(v, tl, tr);
	push_range(v);
	st_add(lv, tl, tm, l, r, val);
	st_add(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void st_max(int v, int tl, int tr, int l, int r, ll val) {
	if(tr < l || tl > r || st[v].mn0 >= val) return;
	if(l <= tl && tr <= r && st[v].mn1 > val) {
		if(tl != tr) push_lazy(v, tl, tr);
		st[v].sum -= st[v].mncnt * (st[v].mn0 - val);
		st[v].mn0 = val;
		st[v].mx0 = max(st[v].mx0, val);
		return;
	}
	push_lazy(v, tl, tr);
	push_range(v);
	st_max(lv, tl, tm, l, r, val);
	st_max(rv, tm + 1, tr, l, r, val);
	pull(v);
}

void st_min(int v, int tl, int tr, int l, int r, ll val) {
	if(tr < l || tl > r || st[v].mx0 <= val) return;
	if(l <= tl && tr <= r && st[v].mx1 < val) {
		if(tl != tr) push_lazy(v, tl, tr);
		st[v].sum -= st[v].mxcnt * (st[v].mx0 - val);
		st[v].mx0 = val;
		st[v].mn0 = min(st[v].mx0, val);
		return;
	}
	push_lazy(v, tl, tr);
	push_range(v);
	st_min(lv, tl, tm, l, r, val);
	st_min(rv, tm + 1, tr, l, r, val);
	pull(v);
}

long long st_query(int v, int tl, int tr, int l, int r) {
	if(tr < l || tl > r) return 0LL;
	if(l <= tl && tr <= r) return st[v].sum;
	push_lazy(v, tl, tr);
	push_range(v);
	return st_query(lv, tl, tm, l, r) + st_query(rv, tm + 1, tr, l, r);
}

void build(int v, int tl, int tr) {
	if(tl == tr) {
		st[v].lazy = st[v].sum = st[v].mn0 = st[v].mx0 = 0;
		st[v].mx1 = -INF;
		st[v].mn1 = INF;
		st[v].mxcnt = st[v].mncnt = 1;
		return;
	}
	build(lv, tl, tm);
	build(rv, tm + 1, tr);
	pull(v);
	st[v].lazy = 0;
}

vector<int> distribute_candies(vector<int> C, vector<int> L, vector<int> R, vector<int> V) {
	int N = C.size();
	int Q = L.size();
	build(0, 0, N - 1);
	for(int i = 0; i < Q; ++i) {
		st_add(0, 0, N - 1, L[i], R[i], V[i]);
		st_min(0, 0, N - 1, L[i], R[i], (ll)C[0]);
		st_max(0, 0, N - 1, L[i], R[i], 0LL);
	}
	vector<int> ans;
	for(int i = 0; i < N; ++i) {
		ans.push_back(st_query(0, 0, N - 1, i, i));
	}
	return ans;
}

/*
int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N, Q; cin >> N >> Q;
	build(0, 0, N - 1);
	for(int i = 0; i < N; ++i) {
		long long x; cin >> x;
		st_add(0, 0, N - 1, i, i, x);
	}
	while(Q--) {
		int t, l, r; cin >> t >> l >> r;
		--r;
		if(t == 3) {
			cout << st_query(0, 0, N - 1, l, r) << '\n';
		} else {
			long long y; cin >> y;
			if(t == 0) st_min(0, 0, N - 1, l, r, y);
			else if(t == 1) st_max(0, 0, N - 1, l, r, y);
			else st_add(0, 0, N - 1, l, r, y);
		}
	}
}*/

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