oj.uz

Submission #736850

# Submission time Handle Problem Language Result Execution time Memory
736850 2023-05-06T09:41:20 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 998 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[10*200000];
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 32 ms 62932 KB Output is correct
2 Correct 27 ms 62872 KB Output is correct
3 Correct 29 ms 62860 KB Output is correct
4 Correct 26 ms 62940 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62932 KB Output is correct
2 Correct 27 ms 62872 KB Output is correct
3 Correct 29 ms 62860 KB Output is correct
4 Correct 26 ms 62940 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct
6 Correct 30 ms 62920 KB Output is correct
7 Correct 31 ms 62892 KB Output is correct
8 Correct 67 ms 63008 KB Output is correct
9 Correct 67 ms 63140 KB Output is correct
10 Correct 62 ms 62904 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62932 KB Output is correct
2 Correct 27 ms 62872 KB Output is correct
3 Correct 29 ms 62860 KB Output is correct
4 Correct 26 ms 62940 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct
6 Correct 846 ms 63852 KB Output is correct
7 Correct 802 ms 64008 KB Output is correct
8 Correct 852 ms 64064 KB Output is correct
9 Correct 998 ms 63976 KB Output is correct
10 Correct 952 ms 63896 KB Output is correct
11 Correct 323 ms 63132 KB Output is correct
12 Correct 318 ms 63200 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 62932 KB Output is correct
2 Correct 27 ms 62872 KB Output is correct
3 Correct 29 ms 62860 KB Output is correct
4 Correct 26 ms 62940 KB Output is correct
5 Correct 27 ms 62888 KB Output is correct
6 Correct 30 ms 62920 KB Output is correct
7 Correct 31 ms 62892 KB Output is correct
8 Correct 67 ms 63008 KB Output is correct
9 Correct 67 ms 63140 KB Output is correct
10 Correct 62 ms 62904 KB Output is correct
11 Correct 846 ms 63852 KB Output is correct
12 Correct 802 ms 64008 KB Output is correct
13 Correct 852 ms 64064 KB Output is correct
14 Correct 998 ms 63976 KB Output is correct
15 Correct 952 ms 63896 KB Output is correct
16 Correct 323 ms 63132 KB Output is correct
17 Correct 318 ms 63200 KB Output is correct
18 Runtime error 289 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -