oj.uz

Submission #736870

# Submission time Handle Problem Language Result Execution time Memory
736870 2023-05-06T09:59:45 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1450 ms 135240 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(0), r(0){}
};
Node tree[40*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(pos <= mid){
			if(tree[node].l == 0)	tree[node].l = cnt++;
			update(tree[node].l, pos, add, l, mid);
		}
		else{
			if(tree[node].r == 0)	tree[node].r = cnt++;
			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 == 0){
		tree[node].l = cnt++;
	}	
	if(tree[node].r == 0)
		tree[node].r = cnt++;
	
	if(L > mid)	return query(tree[node].r, L, R, mid+1, r);
	else if(R <= mid)	return query(tree[node].l, L, R, l, mid);
	else{
		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 55 ms 126128 KB Output is correct
2 Correct 61 ms 126072 KB Output is correct
3 Correct 56 ms 126108 KB Output is correct
4 Correct 61 ms 126284 KB Output is correct
5 Correct 54 ms 126128 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 126128 KB Output is correct
2 Correct 61 ms 126072 KB Output is correct
3 Correct 56 ms 126108 KB Output is correct
4 Correct 61 ms 126284 KB Output is correct
5 Correct 54 ms 126128 KB Output is correct
6 Correct 57 ms 126132 KB Output is correct
7 Correct 58 ms 126104 KB Output is correct
8 Correct 74 ms 126392 KB Output is correct
9 Correct 75 ms 126452 KB Output is correct
10 Correct 76 ms 126432 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 126128 KB Output is correct
2 Correct 61 ms 126072 KB Output is correct
3 Correct 56 ms 126108 KB Output is correct
4 Correct 61 ms 126284 KB Output is correct
5 Correct 54 ms 126128 KB Output is correct
6 Correct 592 ms 127380 KB Output is correct
7 Correct 583 ms 127428 KB Output is correct
8 Correct 669 ms 127396 KB Output is correct
9 Correct 760 ms 127516 KB Output is correct
10 Correct 748 ms 127492 KB Output is correct
11 Correct 296 ms 126612 KB Output is correct
12 Correct 314 ms 126572 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 126128 KB Output is correct
2 Correct 61 ms 126072 KB Output is correct
3 Correct 56 ms 126108 KB Output is correct
4 Correct 61 ms 126284 KB Output is correct
5 Correct 54 ms 126128 KB Output is correct
6 Correct 57 ms 126132 KB Output is correct
7 Correct 58 ms 126104 KB Output is correct
8 Correct 74 ms 126392 KB Output is correct
9 Correct 75 ms 126452 KB Output is correct
10 Correct 76 ms 126432 KB Output is correct
11 Correct 592 ms 127380 KB Output is correct
12 Correct 583 ms 127428 KB Output is correct
13 Correct 669 ms 127396 KB Output is correct
14 Correct 760 ms 127516 KB Output is correct
15 Correct 748 ms 127492 KB Output is correct
16 Correct 296 ms 126612 KB Output is correct
17 Correct 314 ms 126572 KB Output is correct
18 Correct 1242 ms 128420 KB Output is correct
19 Correct 1262 ms 132688 KB Output is correct
20 Correct 1450 ms 135240 KB Output is correct
21 Correct 869 ms 132088 KB Output is correct
22 Correct 303 ms 132220 KB Output is correct
23 Correct 318 ms 132584 KB Output is correct
24 Correct 1233 ms 132492 KB Output is correct