oj.uz

Submission #736837

# Submission time Handle Problem Language Result Execution time Memory
736837 2023-05-06T09:33:30 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1531 ms 510020 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[40 * 200010];
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(l > 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;
			}
			return query(tree[node].r, l, r);
		}
		else if(r <= mid){
			if(tree[node].l == -1){
				tree[node].l = cnt++;
				tree[tree[node].l].tl = tree[node].tl;
				tree[tree[node].l].tr = mid;
			}
			return query(tree[node].l, l, r);
		}
		else{
			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;
			}
			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 103 ms 250772 KB Output is correct
2 Correct 100 ms 250700 KB Output is correct
3 Correct 93 ms 250736 KB Output is correct
4 Correct 95 ms 250784 KB Output is correct
5 Correct 100 ms 250784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 250772 KB Output is correct
2 Correct 100 ms 250700 KB Output is correct
3 Correct 93 ms 250736 KB Output is correct
4 Correct 95 ms 250784 KB Output is correct
5 Correct 100 ms 250784 KB Output is correct
6 Correct 112 ms 250772 KB Output is correct
7 Correct 101 ms 250700 KB Output is correct
8 Correct 126 ms 250792 KB Output is correct
9 Correct 127 ms 251020 KB Output is correct
10 Correct 121 ms 250892 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 250772 KB Output is correct
2 Correct 100 ms 250700 KB Output is correct
3 Correct 93 ms 250736 KB Output is correct
4 Correct 95 ms 250784 KB Output is correct
5 Correct 100 ms 250784 KB Output is correct
6 Correct 819 ms 251800 KB Output is correct
7 Correct 825 ms 251840 KB Output is correct
8 Correct 929 ms 251900 KB Output is correct
9 Correct 1102 ms 251892 KB Output is correct
10 Correct 1000 ms 251964 KB Output is correct
11 Correct 394 ms 251088 KB Output is correct
12 Correct 384 ms 250892 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 250772 KB Output is correct
2 Correct 100 ms 250700 KB Output is correct
3 Correct 93 ms 250736 KB Output is correct
4 Correct 95 ms 250784 KB Output is correct
5 Correct 100 ms 250784 KB Output is correct
6 Correct 112 ms 250772 KB Output is correct
7 Correct 101 ms 250700 KB Output is correct
8 Correct 126 ms 250792 KB Output is correct
9 Correct 127 ms 251020 KB Output is correct
10 Correct 121 ms 250892 KB Output is correct
11 Correct 819 ms 251800 KB Output is correct
12 Correct 825 ms 251840 KB Output is correct
13 Correct 929 ms 251900 KB Output is correct
14 Correct 1102 ms 251892 KB Output is correct
15 Correct 1000 ms 251964 KB Output is correct
16 Correct 394 ms 251088 KB Output is correct
17 Correct 384 ms 250892 KB Output is correct
18 Runtime error 1531 ms 510020 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -