oj.uz

Submission #736867

# Submission time Handle Problem Language Result Execution time Memory
736867 2023-05-06T09:55:10 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1135 ms 257452 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[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(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++;
	
	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 59 ms 126148 KB Output is correct
2 Correct 54 ms 126136 KB Output is correct
3 Correct 54 ms 126172 KB Output is correct
4 Correct 55 ms 126084 KB Output is correct
5 Correct 54 ms 126084 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 126148 KB Output is correct
2 Correct 54 ms 126136 KB Output is correct
3 Correct 54 ms 126172 KB Output is correct
4 Correct 55 ms 126084 KB Output is correct
5 Correct 54 ms 126084 KB Output is correct
6 Correct 59 ms 126096 KB Output is correct
7 Correct 67 ms 126144 KB Output is correct
8 Correct 76 ms 126168 KB Output is correct
9 Correct 76 ms 126156 KB Output is correct
10 Correct 82 ms 126232 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 126148 KB Output is correct
2 Correct 54 ms 126136 KB Output is correct
3 Correct 54 ms 126172 KB Output is correct
4 Correct 55 ms 126084 KB Output is correct
5 Correct 54 ms 126084 KB Output is correct
6 Correct 659 ms 127292 KB Output is correct
7 Correct 649 ms 127224 KB Output is correct
8 Correct 671 ms 127068 KB Output is correct
9 Correct 846 ms 127248 KB Output is correct
10 Correct 777 ms 127184 KB Output is correct
11 Correct 320 ms 126500 KB Output is correct
12 Correct 332 ms 126368 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 126148 KB Output is correct
2 Correct 54 ms 126136 KB Output is correct
3 Correct 54 ms 126172 KB Output is correct
4 Correct 55 ms 126084 KB Output is correct
5 Correct 54 ms 126084 KB Output is correct
6 Correct 59 ms 126096 KB Output is correct
7 Correct 67 ms 126144 KB Output is correct
8 Correct 76 ms 126168 KB Output is correct
9 Correct 76 ms 126156 KB Output is correct
10 Correct 82 ms 126232 KB Output is correct
11 Correct 659 ms 127292 KB Output is correct
12 Correct 649 ms 127224 KB Output is correct
13 Correct 671 ms 127068 KB Output is correct
14 Correct 846 ms 127248 KB Output is correct
15 Correct 777 ms 127184 KB Output is correct
16 Correct 320 ms 126500 KB Output is correct
17 Correct 332 ms 126368 KB Output is correct
18 Runtime error 1135 ms 257452 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -