oj.uz

Submission #940293

# Submission time Handle Problem Language Result Execution time Memory
940293 2024-03-07T07:37:51 Z noyancanturk Happiness (Balkan15_HAPPINESS) C++17
10 / 100
 473 ms 524288 KB 
#include "happiness.h"

#include <bits/stdc++.h>

int64_t P,sgn;
int64_t R;

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

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 int64_t query(int r){
		R=r;
		return root->query(1,n);
	}
};

segtree*st;

int64_t onecount=0;
std::multiset<int>mp;

inline bool isok(){
	int64_t cur=onecount+1,sum=st->root->sum;
	if(!sum)return 1;
	if(!onecount)return 0;
	while(cur<sum){
		int 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 344 KB Output is correct
2 Correct 0 ms 344 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 Runtime error 473 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 Incorrect 271 ms 26448 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 Runtime error 473 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -