oj.uz

답안 #736841

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
736841 2023-05-06T09:38:23 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 93 ms 250772 KB 
#include "happiness.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
long long mx;
struct Node{
	long long sum, tl, tr;
	int l, r;
	Node() : sum(0), l(-1), r(-1){}
};
Node tree[40 * 200010];
int cnt = 2;
void update(int node, long long pos, long long add){
	if(tree[node].tl == tree[node].tr && tree[node].tl == pos){
		tree[node].sum += add;
		return;
	}
	else{
		long long mid = (tree[node].tl + tree[node].tr) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(pos <= mid){
			update(tree[node].l, pos, add);
		}
		else
			update(tree[node].r, pos, add);
			
		tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
	}
}
long long query(int node, int l, int r){
	if(l == tree[node].tl && r == tree[node].tr){
		return tree[node].sum;	
	}
	else{
		int mid = (tree[node].tl + tree[node].tr )/2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
			tree[tree[node].l].tl = tree[node].tl;
			tree[tree[node].l].tr = mid;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
			tree[tree[node].r].tl = mid+1;
			tree[tree[node].r].tr = tree[node].tr;
		}
		if(l > mid)	return query(tree[node].r, l, r);
		else if(r <= mid)	return query(tree[node].l, l, r);
		else{
			return query(tree[node].l, l, mid) + query(tree[node].r, mid+1, r);
		}
	}
}
bool check(){
	long long coin = 1, tot = query(1, 1, mx);
	while(coin <= mx){
		long long sum = query(1, 1, coin);
		if(sum + 1 > mx)	return true;
		if(tot == sum)	return true;
		if(query(1, coin+1, sum+1) == 0)	return false;
		coin = sum + 1;
	}
	return true;
}
bool init(int n, long long M, long long a[]){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	mx = M;
	tree[1].sum = 0;
	tree[1].tl = 1;
	tree[1].tr = 1e12;
	for(int i = 0; i < n; i++)
		update(1, a[i], a[i]);
		
	return check();
}
bool is_happy(int e, int n, long long a[]){
	for(int i = 0; i < n; i++)
		update(1, a[i], a[i]*e);
		
	return check();
}

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 250772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 250772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 250772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 93 ms 250772 KB Output isn't correct
2 Halted 0 ms 0 KB -