Submission #804845

#	Time	Username	Problem	Language	Result	Execution time	Memory
804845		enerelt14	사탕 분배 (IOI21_candies)	C++17	0 / 100	711 ms	26900 KiB

candies

#include "candies.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#define ll long long
using namespace std;

const int MX = 2e5 + 5;

struct T{
	int mx1, mx2;
	int mn1, mn2;
	ll lazy;
	T() {
		mx1 = 0;
		mx2 = -INT_MAX;
		mn1 = 0;
		mn2 = INT_MAX;
		lazy = 0;
	}
} tree[4 * MX];

int n, q, cc;
vector<int> ans;

void get_value(int id) {
	if(tree[id * 2 + 1].mx1 == tree[id * 2 + 2].mx1) {
		tree[id].mx1 = tree[id * 2 + 1].mx1;
		tree[id].mx2 = max(tree[id * 2 + 1].mx2, tree[id * 2 + 2].mx2);
	}
	if(tree[id * 2 + 1].mx1 < tree[id * 2 + 2].mx1) {
		tree[id].mx1 = tree[id * 2 + 2].mx1;
		tree[id].mx2 = max(tree[id * 2 + 1].mx1, tree[id * 2 + 2].mx2);
	}
	if(tree[id * 2 + 1].mx1 > tree[id * 2 + 2].mx1) {
		tree[id].mx1 = tree[id * 2 + 1].mx1;
		tree[id].mx2 = max(tree[id * 2 + 2].mx1, tree[id * 2 + 1].mx2);
	}
	if(tree[id * 2 + 1].mn1 == tree[id * 2 + 2].mn1) {
		tree[id].mn1 = tree[id * 2 + 1].mn1;
		tree[id].mn2 = min(tree[id * 2 + 1].mn2, tree[id * 2 + 2].mn2);
	}
	if(tree[id * 2 + 1].mn1 < tree[id * 2 + 2].mn1) {
		tree[id].mn1 = tree[id * 2 + 2].mn1;
		tree[id].mn2 = min(tree[id * 2 + 1].mn1, tree[id * 2 + 2].mn2);
	}
	if(tree[id * 2 + 1].mn1 > tree[id * 2 + 2].mn1) {
		tree[id].mn1 = tree[id * 2 + 1].mn1;
		tree[id].mn2 = min(tree[id * 2 + 2].mn1, tree[id * 2 + 1].mn2);
	}
}

void propagate(int id, int l, int r) {
	if(l == r || !tree[id].lazy) return;
	tree[id * 2 + 1].lazy += tree[id].lazy;
	tree[id * 2 + 1].mx1 += tree[id].lazy;
	tree[id * 2 + 1].mx1 = min(tree[id * 2 + 1].mx1, tree[id].mx1);
	tree[id * 2 + 1].mx1 = max(tree[id * 2 + 1].mx1, tree[id].mn1);
	tree[id * 2 + 1].mn1 += tree[id].lazy;
	tree[id * 2 + 1].mn1 = max(tree[id * 2 + 1].mn1, tree[id].mn1);
	tree[id * 2 + 1].mn1 = min(tree[id * 2 + 1].mn1, tree[id].mx1);
	if(tree[id * 2 + 1].mx1 != tree[id * 2 + 1].mn1) {
		if(tree[id * 2 + 1].mx2 != -INT_MAX) {
			tree[id * 2 + 1].mx2 += tree[id].lazy;
			tree[id * 2 + 1].mx2 = min(tree[id * 2 + 1].mx2, tree[id * 2 + 1].mx1);
		}
		if(tree[id * 2 + 1].mn2 != INT_MAX) {
			tree[id * 2 + 1].mn2 += tree[id].lazy;
			tree[id * 2 + 1].mn2 = max(tree[id * 2 + 1].mn2, tree[id * 2 + 1].mn1);
		}
	}
	tree[id * 2 + 2].lazy += tree[id].lazy;
	tree[id * 2 + 2].mx1 += tree[id].lazy;
	tree[id * 2 + 2].mx1 = min(tree[id * 2 + 2].mx1, tree[id].mx1);
	tree[id * 2 + 2].mx1 = max(tree[id * 2 + 2].mx1, tree[id].mn1);
	tree[id * 2 + 2].mn1 += tree[id].lazy;
	tree[id * 2 + 2].mn1 = max(tree[id * 2 + 2].mn1, tree[id].mn1);
	tree[id * 2 + 2].mn1 = min(tree[id * 2 + 2].mn1, tree[id].mx1);
	if(tree[id * 2 + 2].mx1 != tree[id * 2 + 2].mn1) {
		if(tree[id * 2 + 2].mx2 != -INT_MAX) {
			tree[id * 2 + 2].mx2 += tree[id].lazy;
			tree[id * 2 + 2].mx2 = min(tree[id * 2 + 2].mx2, tree[id * 2 + 2].mx1);
		}
		if(tree[id * 2 + 2].mn2 != INT_MAX) {
			tree[id * 2 + 2].mn2 += tree[id].lazy;
			tree[id * 2 + 2].mn2 = max(tree[id * 2 + 2].mn2, tree[id * 2 + 2].mn1);
		}
	}
	tree[id].lazy = 0;
	get_value(id);
}

void add(int id, int l, int r, int L, int R, int x) {
	if(L > r || l > R) return;
	if(L <= l && r <= R) {
		tree[id].mx1 += x;
		if(tree[id].mx2 > -INT_MAX) tree[id].mx2 += x;
		tree[id].mn1 += x;
		if(tree[id].mn2 > INT_MAX) tree[id].mn2 += x;
		tree[id].lazy += x;
		return;
	}
	propagate(id, l, r);
	int mid = (l + r) / 2;
	add(id * 2 + 1, l, mid, L, R, x);
	add(id * 2 + 2, mid + 1, r, L, R, x);
	get_value(id);
}

void minn(int id, int l, int r, int L, int R) {
	if(L > r || l > R || tree[id].mx1 <= cc) return;
	if(L <= l && r <= R && tree[id].mx2 < cc) {
		tree[id].mx1 = cc;
		return;
	}
	propagate(id, l, r);
	int mid = (l + r) / 2;
	minn(id * 2 + 1, l, mid, L, R);
	minn(id * 2 + 2, mid + 1, r, L, R);
	get_value(id);
}

void maxx(int id, int l, int r, int L, int R) {
	if(L > r || l > R || tree[id].mn1 >= 0) return;
	if(L <= l && r <= R && tree[id].mn2 > 0) {
		tree[id].mn1 = 0;
		return;
	}
	propagate(id, l, r);
	int mid = (l + r) / 2;
	maxx(id * 2 + 1, l, mid, L, R);
	maxx(id * 2 + 2, mid + 1, r, L, R);
	get_value(id);
}

void solve(int id, int l, int r) {
	if(l == r) {
		ans[l] = tree[id].mx1;
		return;
	}
	propagate(id, l, r);
	int mid = (l + r) / 2;
	solve(id * 2 + 1, l, mid);
	solve(id * 2 + 2, mid + 1, r);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
	n = c.size();
	q = l.size();
	cc = c[0];
	for(int i = 0; i < q; i++) {
		add(0, 0, n - 1, l[i], r[i], v[i]);
		if(v[i] > 0) {
			minn(0, 0, n - 1, l[i], r[i]);
		}
		else {
			maxx(0, 0, n - 1, l[i], r[i]);
		}
	}
	ans.resize(n);
	solve(0, 0, n - 1);
	return ans;
}

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