oj.uz

Submission #736855

# Submission time Handle Problem Language Result Execution time Memory
736855 2023-05-06T09:42:56 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 975 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*201000];
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 23 ms 63188 KB Output is correct
2 Correct 26 ms 63132 KB Output is correct
3 Correct 28 ms 63224 KB Output is correct
4 Correct 25 ms 63188 KB Output is correct
5 Correct 24 ms 63188 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63188 KB Output is correct
2 Correct 26 ms 63132 KB Output is correct
3 Correct 28 ms 63224 KB Output is correct
4 Correct 25 ms 63188 KB Output is correct
5 Correct 24 ms 63188 KB Output is correct
6 Correct 27 ms 63188 KB Output is correct
7 Correct 27 ms 63188 KB Output is correct
8 Correct 53 ms 63292 KB Output is correct
9 Correct 54 ms 63320 KB Output is correct
10 Correct 52 ms 63308 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63188 KB Output is correct
2 Correct 26 ms 63132 KB Output is correct
3 Correct 28 ms 63224 KB Output is correct
4 Correct 25 ms 63188 KB Output is correct
5 Correct 24 ms 63188 KB Output is correct
6 Correct 770 ms 64464 KB Output is correct
7 Correct 755 ms 64228 KB Output is correct
8 Correct 835 ms 64200 KB Output is correct
9 Correct 975 ms 64404 KB Output is correct
10 Correct 901 ms 64340 KB Output is correct
11 Correct 319 ms 63436 KB Output is correct
12 Correct 311 ms 63388 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 63188 KB Output is correct
2 Correct 26 ms 63132 KB Output is correct
3 Correct 28 ms 63224 KB Output is correct
4 Correct 25 ms 63188 KB Output is correct
5 Correct 24 ms 63188 KB Output is correct
6 Correct 27 ms 63188 KB Output is correct
7 Correct 27 ms 63188 KB Output is correct
8 Correct 53 ms 63292 KB Output is correct
9 Correct 54 ms 63320 KB Output is correct
10 Correct 52 ms 63308 KB Output is correct
11 Correct 770 ms 64464 KB Output is correct
12 Correct 755 ms 64228 KB Output is correct
13 Correct 835 ms 64200 KB Output is correct
14 Correct 975 ms 64404 KB Output is correct
15 Correct 901 ms 64340 KB Output is correct
16 Correct 319 ms 63436 KB Output is correct
17 Correct 311 ms 63388 KB Output is correct
18 Runtime error 291 ms 524288 KB Execution killed with signal 9
19 Halted 0 ms 0 KB -