Submission #427609

#	Time	Username	Problem	Language	Result	Execution time	Memory
427609		CSQ31	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1559 ms	372248 KiB

happiness

#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll lf,rg,sum;
	node *l,*r;
	node(ll _lf,ll _rg){
		l = nullptr;
		r = nullptr;
		sum = 0;
		lf = _lf;
		rg = _rg;
	}
	void upd(ll val,ll c){
		sum+=val*c;
		if(lf==rg)return;
		ll tm = (lf+rg)/2;
		if(val<=tm){
			if(l == nullptr)l = new node(lf,tm);
			l->upd(val,c);
		}else{
			if(r == nullptr)r = new node(tm+1,rg);
			r->upd(val,c);
		}
	}
	long long query(long long a, long long b) {
		if (rg < a || lf > b) return 0;
		if (rg <= b && lf >= a) return sum;
		long long ret = 0;
		if (l) ret += l->query(a, b);
		if (r) ret += r->query(a, b);
		return ret;
	}
};
ll m;
node *root;
bool check(){
	ll cur = 1,mx = root->sum;
	while(cur<mx){
		ll t = root->query(1,cur);
		if(cur>t)return false;
		cur = t+1;
	}
	return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
    root = new node(1,m);	
	for(int i=0;i<coinsCount;i++)root->upd(coins[i],1);
	return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0;i<coinsCount;i++)root->upd(coins[i],event);
	return check();
}

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