oj.uz

Submission #940295

# Submission time Handle Problem Language Result Execution time Memory
940295 2024-03-07T07:40:23 Z noyancanturk Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 854 ms 256600 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 16 ms 9564 KB Output is correct
9 Correct 16 ms 9812 KB Output is correct
10 Correct 15 ms 9260 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 197 ms 23376 KB Output is correct
7 Correct 201 ms 26196 KB Output is correct
8 Correct 214 ms 26452 KB Output is correct
9 Correct 358 ms 34492 KB Output is correct
10 Correct 328 ms 36948 KB Output is correct
11 Correct 122 ms 26192 KB Output is correct
12 Correct 115 ms 26336 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 1372 KB Output is correct
7 Correct 2 ms 1372 KB Output is correct
8 Correct 16 ms 9564 KB Output is correct
9 Correct 16 ms 9812 KB Output is correct
10 Correct 15 ms 9260 KB Output is correct
11 Correct 197 ms 23376 KB Output is correct
12 Correct 201 ms 26196 KB Output is correct
13 Correct 214 ms 26452 KB Output is correct
14 Correct 358 ms 34492 KB Output is correct
15 Correct 328 ms 36948 KB Output is correct
16 Correct 122 ms 26192 KB Output is correct
17 Correct 115 ms 26336 KB Output is correct
18 Correct 566 ms 152912 KB Output is correct
19 Correct 553 ms 158716 KB Output is correct
20 Correct 854 ms 256600 KB Output is correct
21 Correct 540 ms 135144 KB Output is correct
22 Correct 160 ms 28244 KB Output is correct
23 Correct 165 ms 28664 KB Output is correct
24 Correct 496 ms 146772 KB Output is correct