oj.uz

Submission #736836

# Submission time Handle Problem Language Result Execution time Memory
736836 2023-05-06T09:30:40 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1515 ms 514416 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(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(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 105 ms 250700 KB Output is correct
2 Correct 108 ms 250776 KB Output is correct
3 Correct 94 ms 250812 KB Output is correct
4 Correct 96 ms 250768 KB Output is correct
5 Correct 101 ms 250800 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 250700 KB Output is correct
2 Correct 108 ms 250776 KB Output is correct
3 Correct 94 ms 250812 KB Output is correct
4 Correct 96 ms 250768 KB Output is correct
5 Correct 101 ms 250800 KB Output is correct
6 Correct 93 ms 250752 KB Output is correct
7 Correct 94 ms 250772 KB Output is correct
8 Correct 126 ms 250900 KB Output is correct
9 Correct 126 ms 250892 KB Output is correct
10 Correct 122 ms 250876 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 250700 KB Output is correct
2 Correct 108 ms 250776 KB Output is correct
3 Correct 94 ms 250812 KB Output is correct
4 Correct 96 ms 250768 KB Output is correct
5 Correct 101 ms 250800 KB Output is correct
6 Correct 820 ms 251904 KB Output is correct
7 Correct 800 ms 251780 KB Output is correct
8 Correct 912 ms 251820 KB Output is correct
9 Correct 1068 ms 251792 KB Output is correct
10 Correct 959 ms 251792 KB Output is correct
11 Correct 388 ms 250956 KB Output is correct
12 Correct 383 ms 250968 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 250700 KB Output is correct
2 Correct 108 ms 250776 KB Output is correct
3 Correct 94 ms 250812 KB Output is correct
4 Correct 96 ms 250768 KB Output is correct
5 Correct 101 ms 250800 KB Output is correct
6 Correct 93 ms 250752 KB Output is correct
7 Correct 94 ms 250772 KB Output is correct
8 Correct 126 ms 250900 KB Output is correct
9 Correct 126 ms 250892 KB Output is correct
10 Correct 122 ms 250876 KB Output is correct
11 Correct 820 ms 251904 KB Output is correct
12 Correct 800 ms 251780 KB Output is correct
13 Correct 912 ms 251820 KB Output is correct
14 Correct 1068 ms 251792 KB Output is correct
15 Correct 959 ms 251792 KB Output is correct
16 Correct 388 ms 250956 KB Output is correct
17 Correct 383 ms 250968 KB Output is correct
18 Runtime error 1515 ms 514416 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -