Submission #409731

#	Time	Username	Problem	Language	Result	Execution time	Memory
409731		codebuster_10	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	1771 ms	508732 KiB

happiness

#include <bits/stdc++.h>
 
using namespace std ;
 
#define int int64_t 
struct Node {
	int sum, tl, tr;
#undef int
	int l, r;// node cover [tl,tr], also lazy is not added to current node;
#define int int64_t
	Node() : sum(0), l(-1), r(-1) {}
};
 
const int BEST = 1.62e7;
Node st[BEST];
int cnt = 2;
 
 
void update(int x, int l, int r, int val) {
	if (l == st[x].tl && r == st[x].tr) {
		st[x].sum += val;
		assert(l == r);
	} else {
		int mid = (st[x].tl + st[x].tr) / 2;
		if (st[x].l == -1) {
			st[x].l = cnt++;
			st[st[x].l].tl = st[x].tl;
			st[st[x].l].tr = mid;
		}
		if (st[x].r == -1) {
			st[x].r = cnt++;
			st[st[x].r].tl = mid + 1;
			st[st[x].r].tr = st[x].tr;
		}
 
		if (l > mid) update(st[x].r, l, r, val);
		else if (r <= mid) update(st[x].l, l, r, val);
		else {
			update(st[x].l, l, mid, val);
			update(st[x].r, mid + 1, r, val);
		}
		st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
	}
}
 
int query(int x, int l, int r) {
	if (l <= st[x].tl && st[x].tr <= r) return st[x].sum;
	else {
		int mid = (st[x].tl + st[x].tr) / 2;
		if (st[x].l == -1) {
			st[x].l = cnt++;
			st[st[x].l].tl = st[x].tl;
			st[st[x].l].tr = mid;
		}
		if (st[x].r == -1) {
			st[x].r = cnt++;
			st[st[x].r].tl = mid + 1;
			st[st[x].r].tr = st[x].tr;
		}
		if (l > mid) return query(st[x].r, l, r);
		else if (r <= mid) return query(st[x].l, l, r);
		else return query(st[x].l, l, r) + query(st[x].r, l, r);
	}
}
 
int W;
 
bool go(){
	for(int x = 1; x < W;){
		int res = query(1,1,x);
		if(res < x)	return false;
		x = res + 1;
	}
	return true;
}
	
#undef int
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
#define int int64_t
  st[1].tl = 1, st[1].tr = maxCoinSize;
	for(int i = 0; i < coinsCount; ++i){
		update(1,coins[i],coins[i],coins[i]);
		W += coins[i];
	}
	return go();
}
 
#undef int
bool is_happy(int event, int coinsCount, long long coins[]) {
#define int int64_t 
	if(event == -1){
		for(int i = 0; i < coinsCount; ++i){
			update(1,coins[i],coins[i],-coins[i]);
			W -= coins[i];
		}
	}else{
		for(int i = 0; i < coinsCount; ++i){
			update(1,coins[i],coins[i],coins[i]);
			W += coins[i];
		}
	}
	return go();
#undef int
}
 
 

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~

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