oj.uz

Submission #736844

# Submission time Handle Problem Language Result Execution time Memory
736844 2023-05-06T09:39:34 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1541 ms 503880 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[64*123456];
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 99 ms 247668 KB Output is correct
2 Correct 97 ms 247636 KB Output is correct
3 Correct 93 ms 247628 KB Output is correct
4 Correct 93 ms 247660 KB Output is correct
5 Correct 113 ms 247676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 247668 KB Output is correct
2 Correct 97 ms 247636 KB Output is correct
3 Correct 93 ms 247628 KB Output is correct
4 Correct 93 ms 247660 KB Output is correct
5 Correct 113 ms 247676 KB Output is correct
6 Correct 97 ms 247712 KB Output is correct
7 Correct 97 ms 247756 KB Output is correct
8 Correct 126 ms 247884 KB Output is correct
9 Correct 145 ms 247704 KB Output is correct
10 Correct 118 ms 247732 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 247668 KB Output is correct
2 Correct 97 ms 247636 KB Output is correct
3 Correct 93 ms 247628 KB Output is correct
4 Correct 93 ms 247660 KB Output is correct
5 Correct 113 ms 247676 KB Output is correct
6 Correct 872 ms 248644 KB Output is correct
7 Correct 897 ms 248772 KB Output is correct
8 Correct 964 ms 248660 KB Output is correct
9 Correct 1068 ms 248876 KB Output is correct
10 Correct 1055 ms 248896 KB Output is correct
11 Correct 384 ms 247792 KB Output is correct
12 Correct 422 ms 247832 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 247668 KB Output is correct
2 Correct 97 ms 247636 KB Output is correct
3 Correct 93 ms 247628 KB Output is correct
4 Correct 93 ms 247660 KB Output is correct
5 Correct 113 ms 247676 KB Output is correct
6 Correct 97 ms 247712 KB Output is correct
7 Correct 97 ms 247756 KB Output is correct
8 Correct 126 ms 247884 KB Output is correct
9 Correct 145 ms 247704 KB Output is correct
10 Correct 118 ms 247732 KB Output is correct
11 Correct 872 ms 248644 KB Output is correct
12 Correct 897 ms 248772 KB Output is correct
13 Correct 964 ms 248660 KB Output is correct
14 Correct 1068 ms 248876 KB Output is correct
15 Correct 1055 ms 248896 KB Output is correct
16 Correct 384 ms 247792 KB Output is correct
17 Correct 422 ms 247832 KB Output is correct
18 Runtime error 1541 ms 503880 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -