| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1210400 | hashdfdfh | Happiness (Balkan15_HAPPINESS) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define int long long
// Index Implementation
const int MAX_M = 1e12 + 5;
const int MAX_Q = 1e5 + 5;
const int DEFAULT = 0;
// 线段树每个节点的内容
struct node {
// 保存数值
int value = DEFAULT;
// lazy标记
int lazy = 0;
// 左侧节点
int left = -1;
// 右侧节点
int right = -1;
};
class SumSegmentTree {
private:
int len;
// 整个线段树
vector<node> tree;
// 目前用到那个idx
int curidx = 0;
// 合并两个结果
int combine(int x, int y) {
return x + y;
}
// 把lazy的结果，应用到at上
// len代表需要更新的区间大小，add需要需要更新的数值
void apply(int cur, int len, int add) {
tree[cur].value += len * add;
tree[cur].lazy += add;
}
// 把lazy的数值，pushdown到at的children
void pushdown(int cur, int at_left, int at_right) {
// 找到mid
int 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(int start, int end, int val, int cur, int at_left, int 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
int 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);
}
// 查询操作
int query(int start, int end, int cur, int at_left, int 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);
int mid = (at_left + at_right) / 2;
// 计算左边
int resl = query(start, end, tree[cur].left, at_left, mid);
// 计算右边
int resr = query(start, end, tree[cur].right, mid + 1, at_right);
// 返回总和
return combine(resl, resr);
}
public:
SumSegmentTree(int len, int q) : len(len) {
if (q > 0) { tree.reserve(2 * q * ceil(log2(len))); }
// 放入一个node，作为root
tree.push_back(node());
curidx++;
}
// 更新操作
void update(int start, int end, int val) {
update(start, end, val, 0, 0, len - 1);
}
// 查询操作
int query(int start, int end) {
return query(start, end, 0, 0, len - 1);
}
};
SumSegmentTree sst(MAX_M, MAX_Q);
void check() {
// k从最小的k开始验证，直到总和
int sum = sst.query(1, MAX_M);
int k = 1;
while (k < sum) {
// 查询所有<=k的数据总和
int cur = sst.query(1, k);
// 说明肯定不happy
if (cur < k) {
cout << 0 << endl;
return;
}
// 否则下一轮的k就是cur+1
k = cur + 1;
}
// 说明是happy
cout << 1 << endl;
}
signed main() {
int n, maxsize;
cin >> n >> maxsize;
// 读取初始的n个banknotes
int b;
for (int i = 0; i < n; ++i) {
cin >> b;
sst.update(b, b, b);
}
// 每次是否是happy
check();
int q;
cin >> q;
// 读q次查询
int type, m, tmp;
for (int i = 0; i < q; ++i) {
cin >> type >> m;
// 如果是新增
if (type == 1) {
for (int j = 0; j < m; ++j) {
cin >> tmp;
sst.update(tmp, tmp, tmp);
}
}
// 如果是删除
else {
for (int j = 0; j < m; ++j) {
cin >> tmp;
sst.update(tmp, tmp, -tmp);
}
}
// 每次计算是否是happy
check();
}
}