Submission #1210408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210408		hashdfdfh	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1958 ms	502392 KiB

happiness

#include "happiness.h"
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Index Implementation

const long long MAX_M = 1e12 + 5;
const long long MAX_Q = 1e5 + 5;
const long long DEFAULT = 0;

// 线段树每个节点的内容
struct node {
	// 保存数值
	long long value = DEFAULT;

	// lazy标记
	long long lazy = 0;

	// 左侧节点
	long long left = -1;

	// 右侧节点
	long long right = -1;
};

class SumSegmentTree {
private:
	long long len;

	// 整个线段树
	vector<node> tree;

	// 目前用到那个idx
	long long curidx = 0;

	// 合并两个结果
	long long combine(long long x, long long y) {
		return x + y;
	}

	// 把lazy的结果，应用到at上
	// len代表需要更新的区间大小，add需要需要更新的数值
	void apply(long long cur, long long len, long long add) {
		tree[cur].value += len * add;
		tree[cur].lazy += add;
	}

	// 把lazy的数值，pushdown到at的children
	void pushdown(long long cur, long long at_left, long long at_right) {
		// 找到mid
		long long mid = (at_left + at_right) / 2;

		// 左侧
		// 先确定已经存在左侧
		if (tree[cur].left == -1) {
			tree[cur].left = curidx++;
			tree.push_back(node());
		}
		apply(tree[cur].left, mid - at_left + 1, tree[cur].lazy);

		// 右侧
		// 先确定已经存在右侧
		if (tree[cur].right == -1) {
			tree[cur].right = curidx++;
			tree.push_back(node());
		}
		apply(tree[cur].right, at_right - mid, tree[cur].lazy);

		// at的lazy重置为0，表示已经pushdown完成
		tree[cur].lazy = 0;
	}

	// 更新操作
	void update(long long start, long long end, long long val, long long cur, long long at_left, long long at_right) {
		// 终止条件
		// 1、完全在[start,end]范围内
		if (start <= at_left && at_right <= end) {
			apply(cur, at_right - at_left + 1, val);
			return;
		}

		// 2、完全不在[start,end]范围内，不需要更新
		if (at_right < start || end < at_left) {
			return;
		}

		// 先pushdown，再继续
		pushdown(cur, at_left, at_right);

		// 找到mid
		long long mid = (at_left + at_right) / 2;

		// 左侧
		update(start, end, val, tree[cur].left, at_left, mid);

		// 右侧
		update(start, end, val, tree[cur].right, mid + 1, at_right);

		// 更新本身
		tree[cur].value = combine(tree[tree[cur].left].value, tree[tree[cur].right].value);
	}

	// 查询操作
	long long query(long long start, long long end, long long cur, long long at_left, long long at_right) {
		// 终止条件
		// 1、完全在[start,end]范围内
		if (start <= at_left && at_right <= end) {
			return tree[cur].value;
		}

		// 2、完全不在[start,end]范围内
		if (at_right < start || end < at_left) {
			return DEFAULT;
		}

		// 先pushdown，再继续
		pushdown(cur, at_left, at_right);

		long long mid = (at_left + at_right) / 2;

		// 计算左边
		long long resl = query(start, end, tree[cur].left, at_left, mid);

		// 计算右边
		long long resr = query(start, end, tree[cur].right, mid + 1, at_right);

		// 返回总和
		return combine(resl, resr);
	}

public:
	SumSegmentTree(long long len, long long q) : len(len) {
		if (q > 0) { tree.reserve(2 * q * ceil(log2(len))); }

		// 放入一个node，作为root
		tree.push_back(node());
		curidx++;
	}

	// 更新操作
	void update(long long start, long long end, long long val) {
		update(start, end, val, 0, 0, len - 1);
	}

	// 查询操作
	long long query(long long start, long long end) {
		return query(start, end, 0, 0, len - 1);
	}
};

SumSegmentTree sst(MAX_M, MAX_Q);

bool check() {
	// k从最小的k开始验证，直到总和
	long long sum = sst.query(1, MAX_M);
	long long k = 1;

	while (k < sum) {
		// 查询所有<=k的数据总和
		long long cur = sst.query(1, k);

		// 说明肯定不happy
		if (cur < k) {
			return false;
		}

		// 否则下一轮的k就是cur+1
		k = cur + 1;
	}

	// 说明是happy
	return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	long long b;
	for (int i = 0; i < coinsCount; ++i) {
		b = coins[i];
		sst.update(b, b, b);
	}
	// 是否是happy
	return check();
}

bool is_happy(int event, int coinsCount, long long coins[]) {
	long long tmp;
	// 如果是新增
	if (event == 1) {
		for (int j = 0; j < coinsCount; ++j) {
			tmp = coins[j];
			sst.update(tmp, tmp, tmp);
		}
	}
	// 如果是删除
	else {
		for (int j = 0; j < coinsCount; ++j) {
			tmp = coins[j];
			sst.update(tmp, tmp, -tmp);
		}
	}

	// 每次计算是否是happy
	return check();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40