Submission #940295

#	Time	Username	Problem	Language	Result	Execution time	Memory
940295		noyancanturk	Happiness (Balkan15_HAPPINESS)	C++17	100 / 100	854 ms	256600 KiB

happiness

#include "happiness.h"

#include <bits/stdc++.h>

uint64_t P,sgn;
uint64_t R;

struct node{
	uint64_t sum=0;
	node*left=0,*right=0;
	inline node(){}
	inline void update(uint64_t l,uint64_t r){
		if(l==r){
			sum+=P*sgn;
			return;
		}
		uint64_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;
		if(left){
			sum=left->sum;
		}
		if(right){
			sum+=right->sum;
		}
	}
	inline uint64_t query(uint64_t l,uint64_t r){
		if(l==r){
			return sum;
		}
		uint64_t mid=(l+r)>>1;
		if(R<=mid){
			if(!left)return 0;
			return left->query(l,mid);
		}
		uint64_t ans=0;
		if(left)ans=left->sum;
		if(right)ans+=right->query(mid+1,r);
		return ans;
	}
};

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

segtree*st;

uint64_t onecount=0;

inline bool isok(){
	uint64_t cur=onecount+1,sum=st->root->sum;
	if(!sum)return 1;
	if(!onecount)return 0;
	while(cur<sum){
		uint64_t ccur=st->query(cur);
		if(ccur<cur){
			return 0;
		}
		cur=ccur+1;
	}
	return 1;
}

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

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