oj.uz

Submission #736833

# Submission time Handle Problem Language Result Execution time Memory
736833 2023-05-06T09:27:45 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1933 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[]){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	mx = M;
	tree[1].sum = 0;
	tree[1].tl = 0;
	tree[1].tr = 1e12+100;
	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 135 ms 313424 KB Output is correct
2 Correct 115 ms 313428 KB Output is correct
3 Correct 141 ms 313380 KB Output is correct
4 Correct 118 ms 313524 KB Output is correct
5 Correct 117 ms 313332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 313424 KB Output is correct
2 Correct 115 ms 313428 KB Output is correct
3 Correct 141 ms 313380 KB Output is correct
4 Correct 118 ms 313524 KB Output is correct
5 Correct 117 ms 313332 KB Output is correct
6 Correct 122 ms 313348 KB Output is correct
7 Correct 120 ms 313348 KB Output is correct
8 Correct 148 ms 313744 KB Output is correct
9 Correct 152 ms 313668 KB Output is correct
10 Correct 150 ms 313572 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 313424 KB Output is correct
2 Correct 115 ms 313428 KB Output is correct
3 Correct 141 ms 313380 KB Output is correct
4 Correct 118 ms 313524 KB Output is correct
5 Correct 117 ms 313332 KB Output is correct
6 Correct 969 ms 314476 KB Output is correct
7 Correct 942 ms 314584 KB Output is correct
8 Correct 1093 ms 314500 KB Output is correct
9 Correct 1214 ms 314496 KB Output is correct
10 Correct 1100 ms 314740 KB Output is correct
11 Correct 455 ms 313632 KB Output is correct
12 Correct 435 ms 313816 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 313424 KB Output is correct
2 Correct 115 ms 313428 KB Output is correct
3 Correct 141 ms 313380 KB Output is correct
4 Correct 118 ms 313524 KB Output is correct
5 Correct 117 ms 313332 KB Output is correct
6 Correct 122 ms 313348 KB Output is correct
7 Correct 120 ms 313348 KB Output is correct
8 Correct 148 ms 313744 KB Output is correct
9 Correct 152 ms 313668 KB Output is correct
10 Correct 150 ms 313572 KB Output is correct
11 Correct 969 ms 314476 KB Output is correct
12 Correct 942 ms 314584 KB Output is correct
13 Correct 1093 ms 314500 KB Output is correct
14 Correct 1214 ms 314496 KB Output is correct
15 Correct 1100 ms 314740 KB Output is correct
16 Correct 455 ms 313632 KB Output is correct
17 Correct 435 ms 313816 KB Output is correct
18 Runtime error 1933 ms 524288 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -