oj.uz

Submission #736865

# Submission time Handle Problem Language Result Execution time Memory
736865 2023-05-06T09:51:22 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1430 ms 257616 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++;
		
	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 60 ms 126156 KB Output is correct
2 Correct 56 ms 126168 KB Output is correct
3 Correct 53 ms 126156 KB Output is correct
4 Correct 53 ms 126120 KB Output is correct
5 Correct 57 ms 126156 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 126156 KB Output is correct
2 Correct 56 ms 126168 KB Output is correct
3 Correct 53 ms 126156 KB Output is correct
4 Correct 53 ms 126120 KB Output is correct
5 Correct 57 ms 126156 KB Output is correct
6 Correct 72 ms 126128 KB Output is correct
7 Correct 58 ms 126100 KB Output is correct
8 Correct 83 ms 126144 KB Output is correct
9 Correct 81 ms 126192 KB Output is correct
10 Correct 100 ms 126156 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 126156 KB Output is correct
2 Correct 56 ms 126168 KB Output is correct
3 Correct 53 ms 126156 KB Output is correct
4 Correct 53 ms 126120 KB Output is correct
5 Correct 57 ms 126156 KB Output is correct
6 Correct 812 ms 127160 KB Output is correct
7 Correct 828 ms 127332 KB Output is correct
8 Correct 1002 ms 127412 KB Output is correct
9 Correct 1074 ms 127144 KB Output is correct
10 Correct 949 ms 127144 KB Output is correct
11 Correct 341 ms 126252 KB Output is correct
12 Correct 325 ms 126316 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 126156 KB Output is correct
2 Correct 56 ms 126168 KB Output is correct
3 Correct 53 ms 126156 KB Output is correct
4 Correct 53 ms 126120 KB Output is correct
5 Correct 57 ms 126156 KB Output is correct
6 Correct 72 ms 126128 KB Output is correct
7 Correct 58 ms 126100 KB Output is correct
8 Correct 83 ms 126144 KB Output is correct
9 Correct 81 ms 126192 KB Output is correct
10 Correct 100 ms 126156 KB Output is correct
11 Correct 812 ms 127160 KB Output is correct
12 Correct 828 ms 127332 KB Output is correct
13 Correct 1002 ms 127412 KB Output is correct
14 Correct 1074 ms 127144 KB Output is correct
15 Correct 949 ms 127144 KB Output is correct
16 Correct 341 ms 126252 KB Output is correct
17 Correct 325 ms 126316 KB Output is correct
18 Runtime error 1430 ms 257616 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -