oj.uz

Submission #409731

# Submission time Handle Problem Language Result Execution time Memory
409731 2021-05-21T12:04:32 Z codebuster_10 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1771 ms 508732 KB 
#include <bits/stdc++.h>
 
using namespace std ;
 
#define int int64_t 
struct Node {
	int sum, tl, tr;
#undef int
	int l, r;// node cover [tl,tr], also lazy is not added to current node;
#define int int64_t
	Node() : sum(0), l(-1), r(-1) {}
};
 
const int BEST = 1.62e7;
Node st[BEST];
int cnt = 2;
 
 
void update(int x, int l, int r, int val) {
	if (l == st[x].tl && r == st[x].tr) {
		st[x].sum += val;
		assert(l == r);
	} else {
		int mid = (st[x].tl + st[x].tr) / 2;
		if (st[x].l == -1) {
			st[x].l = cnt++;
			st[st[x].l].tl = st[x].tl;
			st[st[x].l].tr = mid;
		}
		if (st[x].r == -1) {
			st[x].r = cnt++;
			st[st[x].r].tl = mid + 1;
			st[st[x].r].tr = st[x].tr;
		}
 
		if (l > mid) update(st[x].r, l, r, val);
		else if (r <= mid) update(st[x].l, l, r, val);
		else {
			update(st[x].l, l, mid, val);
			update(st[x].r, mid + 1, r, val);
		}
		st[x].sum = st[st[x].l].sum + st[st[x].r].sum;
	}
}
 
int query(int x, int l, int r) {
	if (l <= st[x].tl && st[x].tr <= r) return st[x].sum;
	else {
		int mid = (st[x].tl + st[x].tr) / 2;
		if (st[x].l == -1) {
			st[x].l = cnt++;
			st[st[x].l].tl = st[x].tl;
			st[st[x].l].tr = mid;
		}
		if (st[x].r == -1) {
			st[x].r = cnt++;
			st[st[x].r].tl = mid + 1;
			st[st[x].r].tr = st[x].tr;
		}
		if (l > mid) return query(st[x].r, l, r);
		else if (r <= mid) return query(st[x].l, l, r);
		else return query(st[x].l, l, r) + query(st[x].r, l, r);
	}
}
 
int W;
 
bool go(){
	for(int x = 1; x < W;){
		int res = query(1,1,x);
		if(res < x)	return false;
		x = res + 1;
	}
	return true;
}
	
#undef int
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
#define int int64_t
  st[1].tl = 1, st[1].tr = maxCoinSize;
	for(int i = 0; i < coinsCount; ++i){
		update(1,coins[i],coins[i],coins[i]);
		W += coins[i];
	}
	return go();
}
 
#undef int
bool is_happy(int event, int coinsCount, long long coins[]) {
#define int int64_t 
	if(event == -1){
		for(int i = 0; i < coinsCount; ++i){
			update(1,coins[i],coins[i],-coins[i]);
			W -= coins[i];
		}
	}else{
		for(int i = 0; i < coinsCount; ++i){
			update(1,coins[i],coins[i],coins[i]);
			W += coins[i];
		}
	}
	return go();
#undef int
}

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 219 ms 507396 KB Output is correct
2 Correct 209 ms 507460 KB Output is correct
3 Correct 215 ms 507400 KB Output is correct
4 Correct 212 ms 507456 KB Output is correct
5 Correct 212 ms 507528 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 507396 KB Output is correct
2 Correct 209 ms 507460 KB Output is correct
3 Correct 215 ms 507400 KB Output is correct
4 Correct 212 ms 507456 KB Output is correct
5 Correct 212 ms 507528 KB Output is correct
6 Correct 212 ms 507448 KB Output is correct
7 Correct 215 ms 507456 KB Output is correct
8 Correct 236 ms 507592 KB Output is correct
9 Correct 237 ms 507548 KB Output is correct
10 Correct 234 ms 507580 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 507396 KB Output is correct
2 Correct 209 ms 507460 KB Output is correct
3 Correct 215 ms 507400 KB Output is correct
4 Correct 212 ms 507456 KB Output is correct
5 Correct 212 ms 507528 KB Output is correct
6 Correct 671 ms 508696 KB Output is correct
7 Correct 681 ms 508520 KB Output is correct
8 Correct 700 ms 508520 KB Output is correct
9 Correct 868 ms 508532 KB Output is correct
10 Correct 838 ms 508648 KB Output is correct
11 Correct 476 ms 507844 KB Output is correct
12 Correct 433 ms 507812 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 507396 KB Output is correct
2 Correct 209 ms 507460 KB Output is correct
3 Correct 215 ms 507400 KB Output is correct
4 Correct 212 ms 507456 KB Output is correct
5 Correct 212 ms 507528 KB Output is correct
6 Correct 212 ms 507448 KB Output is correct
7 Correct 215 ms 507456 KB Output is correct
8 Correct 236 ms 507592 KB Output is correct
9 Correct 237 ms 507548 KB Output is correct
10 Correct 234 ms 507580 KB Output is correct
11 Correct 671 ms 508696 KB Output is correct
12 Correct 681 ms 508520 KB Output is correct
13 Correct 700 ms 508520 KB Output is correct
14 Correct 868 ms 508532 KB Output is correct
15 Correct 838 ms 508648 KB Output is correct
16 Correct 476 ms 507844 KB Output is correct
17 Correct 433 ms 507812 KB Output is correct
18 Correct 1420 ms 508572 KB Output is correct
19 Correct 1377 ms 508492 KB Output is correct
20 Correct 1771 ms 508648 KB Output is correct
21 Correct 1134 ms 508732 KB Output is correct
22 Correct 634 ms 507776 KB Output is correct
23 Correct 593 ms 507792 KB Output is correct
24 Correct 1347 ms 508456 KB Output is correct