Submission #284064

#	Time	Username	Problem	Language	Result	Execution time	Memory
284064		NaimSS	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1659 ms	256760 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

const ll inf = 1e16;
const ll MAX = (1e12) + 10;
struct node{
  node* c[2];
  ll sum;
  node(){c[0] = c[1] = nullptr;sum = 0;}
  
  void upd(ll p,ll v,ll i = 0, ll j = MAX){
  	if(i == j){
  		sum+=v;
  		return;
  	}
  	ll m = (i + j)/2;
  	if(p<=m){
  		if(!c[0])c[0] = new node();
  		c[0]->upd(p,v,i,m);
  	}else{
  		if(!c[1])c[1] = new node();
  		c[1]->upd(p,v,m+1,j);
  	}
  	sum=(c[0] ? c[0]->sum : 0) + (c[1] ? c[1]->sum : 0);
  }
  ll query(ll a,ll b,ll i = 0,ll j = MAX){
  	if(i > j || i > b || j < a)return 0;
  	if(a<=i and j<=b)return sum;
  	ll m = (i + j)/2;
  	return (c[0] ? c[0]->query(a,b,i,m) : 0) + (c[1] ? c[1]->query(a,b,m+1,j) : 0);
  }
  	
};

node* tree;
ll tot=0;
ll mx = 0;
bool good(){
	ll have = 0;
	while(have < min(mx,tot)){
		ll novo = tree->query(0,have + 1);
		if(novo == have)return 0;
		have = novo;
	}
	return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	tree = new node();
	mx = maxCoinSize;
	tot=0;
	for(int i=0;i<coinsCount;i++){
		ll v = coins[i];
		tree->upd(v,v);
		tot+=v;
	}
	return good();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0;i<coinsCount;i++){
		ll v = coins[i];
		tree->upd(v,v*event);
		tot+=v*event;
	}
	return good();
}

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