oj.uz

Submission #736856

# Submission time Handle Problem Language Result Execution time Memory
736856 2023-05-06T09:44:28 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 995 ms 524288 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[20*201000];
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, long long l, long long r){
	if(tree[node].tl > r || tree[node].tr < l)	return 0;
	if(l == tree[node].tl && tree[node].tr == r) return tree[node].sum;
	else{
		long long mid=(tree[node].tl + tree[node].tr) /2;
		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(tree[node].l == -1){
				tree[node].l = cnt++;
				tree[tree[node].l].tl = tree[node].tl;
				tree[tree[node].l].tr = mid;
			}
		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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 126128 KB Output is correct
2 Correct 54 ms 126156 KB Output is correct
3 Correct 54 ms 126080 KB Output is correct
4 Correct 49 ms 126112 KB Output is correct
5 Correct 53 ms 126196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 126128 KB Output is correct
2 Correct 54 ms 126156 KB Output is correct
3 Correct 54 ms 126080 KB Output is correct
4 Correct 49 ms 126112 KB Output is correct
5 Correct 53 ms 126196 KB Output is correct
6 Correct 56 ms 126196 KB Output is correct
7 Correct 61 ms 126172 KB Output is correct
8 Correct 81 ms 126316 KB Output is correct
9 Correct 81 ms 126288 KB Output is correct
10 Correct 76 ms 126404 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 126128 KB Output is correct
2 Correct 54 ms 126156 KB Output is correct
3 Correct 54 ms 126080 KB Output is correct
4 Correct 49 ms 126112 KB Output is correct
5 Correct 53 ms 126196 KB Output is correct
6 Correct 785 ms 127400 KB Output is correct
7 Correct 748 ms 127336 KB Output is correct
8 Correct 860 ms 127308 KB Output is correct
9 Correct 995 ms 127492 KB Output is correct
10 Correct 939 ms 127516 KB Output is correct
11 Correct 345 ms 126636 KB Output is correct
12 Correct 340 ms 126564 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 126128 KB Output is correct
2 Correct 54 ms 126156 KB Output is correct
3 Correct 54 ms 126080 KB Output is correct
4 Correct 49 ms 126112 KB Output is correct
5 Correct 53 ms 126196 KB Output is correct
6 Correct 56 ms 126196 KB Output is correct
7 Correct 61 ms 126172 KB Output is correct
8 Correct 81 ms 126316 KB Output is correct
9 Correct 81 ms 126288 KB Output is correct
10 Correct 76 ms 126404 KB Output is correct
11 Correct 785 ms 127400 KB Output is correct
12 Correct 748 ms 127336 KB Output is correct
13 Correct 860 ms 127308 KB Output is correct
14 Correct 995 ms 127492 KB Output is correct
15 Correct 939 ms 127516 KB Output is correct
16 Correct 345 ms 126636 KB Output is correct
17 Correct 340 ms 126564 KB Output is correct
18 Runtime error 339 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -