Submission #940249

#	Time	Username	Problem	Language	Result	Execution time	Memory
940249		noyancanturk	Happiness (Balkan15_HAPPINESS)	C++17	0 / 100	1 ms	344 KiB

happiness

#include "happiness.h"

#include <bits/stdc++.h>

int64_t P,sgn;

struct node{
	int64_t sum=0,need=0;
	node*left=0,*right=0;
	inline node(){}
	inline void update(int64_t l,int64_t r){
		if(l==r){
			sum+=P*sgn;
			if(sum)need=P-1;
			return;
		}
		int64_t mid=(l+r)>>1;
		if(P<=mid){
			if(!left)left=new node;
			left->update(l,mid);
		}else{
			if(!right)right=new node;
			right->update(mid+1,r);
		}
		sum=0;
		need=0;
		if(left){
			sum=left->sum;
			need=left->need;
		}
		if(right){
			sum+=right->sum;
			if(left)need=std::max(need,right->need-left->sum);
			else need=right->need;
		}
	}
	inline bool query(int64_t r){
		if(r==1){
			if(sum)return 1;
			return 0;
		}
		if(!left)return 0;
		if(right&&left->sum<right->need){
			return 0;
		}
		return left->query((1+r)>>1);
	}
};

struct segtree{
	int n;
	node*root;
	inline segtree(int n):n(n){
		root=new node;
	}
	inline void update(int p,int s){
		P=p,sgn=s;
		root->update(1,n);
	}
	inline bool query(){
		return root->query(n);
	}
};

segtree*st;

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	st=new segtree(maxCoinSize);
	for(int i=0;i<coinsCount;i++){
		st->update(coins[i],1);
	}
	return st->query();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0;i<coinsCount;i++){
		st->update(coins[i],event);
	}
	return st->query();
}

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: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40