oj.uz

Submission #736864

# Submission time Handle Problem Language Result Execution time Memory
736864 2023-05-06T09:50:18 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1042 ms 129756 KB 
#include "happiness.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
long long mx;
struct Node{
	long long sum;
	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, long long l, long long r){
	if(l == r && l == pos){
		tree[node].sum += add;
	}
	else{
		long long mid = (l+ r) / 2;
		if(tree[node].l == -1){
			tree[node].l = cnt++;
		}
		if(tree[node].r == -1){
			tree[node].r = cnt++;
		}
		if(pos <= mid){
			update(tree[node].l, pos, add, l, mid);
		}
		else
			update(tree[node].r, pos, add, mid+1, r);
			
		tree[node].sum = tree[tree[node].l].sum + tree[tree[node].r].sum;
	}
}
long long query(int node, long long L, long long R, long long l, long long r){
	if(r < L || l > R)	return 0;
	if(L <= l && r <= R)	return tree[node].sum;
	
	long long mid = (l + r) / 2;
	if(tree[node].l == -1){
		tree[node].l = cnt++;
	}	
	if(tree[node].r == -1)
		tree[node].r = cnt++;
		
	return query(tree[node].l, L, R, l, mid) + query(tree[node].r, L, R, mid+1, r);
}
bool check(){
	long long coin = 1, tot = query(1, 1, mx, 1, 1e12);
	while(coin <= mx){
		long long sum = query(1, 1, coin,1,1e12);
		if(sum + 1 > mx)	return true;
		if(tot == sum)	return true;
		if(query(1, coin+1, sum+1,1,1e12) == 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;
	for(int i = 0; i < n; i++)
		update(1, a[i], a[i], 1, 1e12);
		
	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, 1, 1e12);
		
	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 63132 KB Output is correct
2 Correct 28 ms 63140 KB Output is correct
3 Correct 33 ms 63148 KB Output is correct
4 Correct 31 ms 63252 KB Output is correct
5 Correct 27 ms 63188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63132 KB Output is correct
2 Correct 28 ms 63140 KB Output is correct
3 Correct 33 ms 63148 KB Output is correct
4 Correct 31 ms 63252 KB Output is correct
5 Correct 27 ms 63188 KB Output is correct
6 Correct 29 ms 63244 KB Output is correct
7 Correct 29 ms 63280 KB Output is correct
8 Correct 57 ms 63228 KB Output is correct
9 Correct 62 ms 63328 KB Output is correct
10 Correct 57 ms 63320 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63132 KB Output is correct
2 Correct 28 ms 63140 KB Output is correct
3 Correct 33 ms 63148 KB Output is correct
4 Correct 31 ms 63252 KB Output is correct
5 Correct 27 ms 63188 KB Output is correct
6 Correct 863 ms 64280 KB Output is correct
7 Correct 824 ms 64308 KB Output is correct
8 Correct 928 ms 64128 KB Output is correct
9 Correct 1042 ms 64312 KB Output is correct
10 Correct 999 ms 64320 KB Output is correct
11 Correct 315 ms 63436 KB Output is correct
12 Correct 321 ms 63432 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63132 KB Output is correct
2 Correct 28 ms 63140 KB Output is correct
3 Correct 33 ms 63148 KB Output is correct
4 Correct 31 ms 63252 KB Output is correct
5 Correct 27 ms 63188 KB Output is correct
6 Correct 29 ms 63244 KB Output is correct
7 Correct 29 ms 63280 KB Output is correct
8 Correct 57 ms 63228 KB Output is correct
9 Correct 62 ms 63328 KB Output is correct
10 Correct 57 ms 63320 KB Output is correct
11 Correct 863 ms 64280 KB Output is correct
12 Correct 824 ms 64308 KB Output is correct
13 Correct 928 ms 64128 KB Output is correct
14 Correct 1042 ms 64312 KB Output is correct
15 Correct 999 ms 64320 KB Output is correct
16 Correct 315 ms 63436 KB Output is correct
17 Correct 321 ms 63432 KB Output is correct
18 Runtime error 150 ms 129756 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -