oj.uz

Submission #736827

# Submission time Handle Problem Language Result Execution time Memory
736827 2023-05-06T09:23:09 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
40 / 100
 1014 ms 524288 KB 
#include "happiness.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
ll mx;
struct Node{
	ll sum, tl, tr, l, r;
	Node() : sum(0), l(-1), r(-1){}
};
Node tree[40 * 200010];
int cnt = 2;
void update(int node, ll pos, ll add){
	if(tree[node].tl == tree[node].tr && tree[node].tl == pos){
		tree[node].sum += add;
		return;
	}
	else{
		ll 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;
	}
}
ll query(int node, ll l, ll 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{
		ll 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(){
	ll coin = 1, tot = query(1, 1, mx);
	while(coin <= mx){
		ll 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, ll M, ll a[]){
	mx = M;
	tree[1].sum = 0;
	tree[1].tl = 1;
	tree[1].tr = 1e9;
	for(int i = 0; i < n; i++)
		update(1, a[i], a[i]);
		
	return check();
}
bool is_happy(int e, int n, ll 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 119 ms 313312 KB Output is correct
2 Correct 126 ms 313368 KB Output is correct
3 Correct 119 ms 313300 KB Output is correct
4 Correct 125 ms 313340 KB Output is correct
5 Correct 117 ms 313368 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 313312 KB Output is correct
2 Correct 126 ms 313368 KB Output is correct
3 Correct 119 ms 313300 KB Output is correct
4 Correct 125 ms 313340 KB Output is correct
5 Correct 117 ms 313368 KB Output is correct
6 Runtime error 689 ms 524288 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 313312 KB Output is correct
2 Correct 126 ms 313368 KB Output is correct
3 Correct 119 ms 313300 KB Output is correct
4 Correct 125 ms 313340 KB Output is correct
5 Correct 117 ms 313368 KB Output is correct
6 Correct 877 ms 317516 KB Output is correct
7 Correct 831 ms 317536 KB Output is correct
8 Correct 923 ms 317512 KB Output is correct
9 Correct 1014 ms 318936 KB Output is correct
10 Correct 967 ms 318952 KB Output is correct
11 Correct 412 ms 317280 KB Output is correct
12 Correct 425 ms 317384 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 313312 KB Output is correct
2 Correct 126 ms 313368 KB Output is correct
3 Correct 119 ms 313300 KB Output is correct
4 Correct 125 ms 313340 KB Output is correct
5 Correct 117 ms 313368 KB Output is correct
6 Runtime error 689 ms 524288 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -