oj.uz

Submission #736831

# Submission time Handle Problem Language Result Execution time Memory
736831 2023-05-06T09:26:42 Z MODDI Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 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 = 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 146 ms 313308 KB Output is correct
2 Correct 130 ms 313380 KB Output is correct
3 Correct 127 ms 313336 KB Output is correct
4 Correct 123 ms 313372 KB Output is correct
5 Correct 131 ms 313308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 313308 KB Output is correct
2 Correct 130 ms 313380 KB Output is correct
3 Correct 127 ms 313336 KB Output is correct
4 Correct 123 ms 313372 KB Output is correct
5 Correct 131 ms 313308 KB Output is correct
6 Correct 119 ms 313416 KB Output is correct
7 Correct 132 ms 313448 KB Output is correct
8 Correct 190 ms 313692 KB Output is correct
9 Correct 158 ms 313692 KB Output is correct
10 Correct 148 ms 313560 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 313308 KB Output is correct
2 Correct 130 ms 313380 KB Output is correct
3 Correct 127 ms 313336 KB Output is correct
4 Correct 123 ms 313372 KB Output is correct
5 Correct 131 ms 313308 KB Output is correct
6 Correct 1048 ms 314492 KB Output is correct
7 Correct 979 ms 314492 KB Output is correct
8 Correct 1089 ms 314604 KB Output is correct
9 Correct 1281 ms 314704 KB Output is correct
10 Correct 1125 ms 314536 KB Output is correct
11 Correct 451 ms 313744 KB Output is correct
12 Correct 472 ms 313928 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 313308 KB Output is correct
2 Correct 130 ms 313380 KB Output is correct
3 Correct 127 ms 313336 KB Output is correct
4 Correct 123 ms 313372 KB Output is correct
5 Correct 131 ms 313308 KB Output is correct
6 Correct 119 ms 313416 KB Output is correct
7 Correct 132 ms 313448 KB Output is correct
8 Correct 190 ms 313692 KB Output is correct
9 Correct 158 ms 313692 KB Output is correct
10 Correct 148 ms 313560 KB Output is correct
11 Correct 1048 ms 314492 KB Output is correct
12 Correct 979 ms 314492 KB Output is correct
13 Correct 1089 ms 314604 KB Output is correct
14 Correct 1281 ms 314704 KB Output is correct
15 Correct 1125 ms 314536 KB Output is correct
16 Correct 451 ms 313744 KB Output is correct
17 Correct 472 ms 313928 KB Output is correct
18 Execution timed out 2062 ms 524288 KB Time limit exceeded
19 Halted 0 ms 0 KB -