oj.uz

Submission #538360

# Submission time Handle Problem Language Result Execution time Memory
538360 2022-03-16T16:20:05 Z fcw Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 1850 ms 395380 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;

using lint = long long;
lint LIM = 1e12 + 10;

struct node{
	lint sum, lz;
	int l, r;
	node(): sum(0), lz(0), l(0), r(0) {}
};

vector<node>seg;

int create(){
	seg.push_back(node());
	return seg.size() - 1;
}

void push(int v, lint l, lint r){
}

void update(int v, lint l, lint r, lint a, lint b, lint val){
	if(b < l || r < a) return;
	push(v, l, r);
	if(a <= l && r <= b){
		seg[v].sum += val;
		push(v, l, r);
		return;
	}
	lint m = (l + r) >> 1;
	if(!seg[v].l){
		int aux = create();
		seg[v].l = aux;
	}
	if(!seg[v].r){
		int aux = create();
		seg[v].r = aux;
	}
	update(seg[v].l, l, m, a, b, val);
	update(seg[v].r, m+1, r, a, b, val);
	push(seg[v].l, l, m);
	push(seg[v].r, m+1, r);
	seg[v].sum = seg[seg[v].l].sum + seg[seg[v].r].sum;
}

lint query(int v, lint l, lint r, lint a, lint b){
	if(b < l || r < a) return 0;
	if(v == 0) return 0;
	push(v, l, r);
	if(a <= l && r <= b){
		return seg[v].sum;
	}
	lint m = (l + r) >> 1;
	return query(seg[v].l, l, m, a, b) + query(seg[v].r, m+1, r, a, b);
}

bool check(){
	lint cur = 0, sum = seg[1].sum;
	while(cur < sum){
		lint cnt = query(1, 1, LIM, 1, cur);
		if(cnt < cur) return 0;
		cur = cnt + 1;
	}
	return 1;
}

bool init(int coinsCount, lint maxCoinSize, lint coins[]) {
	create();
	create();
	for(int i=0;i<coinsCount;i++){
		update(1, 1, LIM, coins[i], coins[i], coins[i]);
	}
	return check();
}

bool is_happy(int event, int coinsCount, lint coins[]) {
	for(int i=0;i<coinsCount;i++){
		update(1, 1, LIM, coins[i], coins[i], coins[i] * event);
	}
	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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 5 ms 3528 KB Output is correct
8 Correct 43 ms 25184 KB Output is correct
9 Correct 39 ms 25060 KB Output is correct
10 Correct 37 ms 25064 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 699 ms 50564 KB Output is correct
7 Correct 597 ms 25868 KB Output is correct
8 Correct 752 ms 50544 KB Output is correct
9 Correct 970 ms 50532 KB Output is correct
10 Correct 887 ms 50504 KB Output is correct
11 Correct 290 ms 25200 KB Output is correct
12 Correct 281 ms 25144 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 1996 KB Output is correct
7 Correct 5 ms 3528 KB Output is correct
8 Correct 43 ms 25184 KB Output is correct
9 Correct 39 ms 25060 KB Output is correct
10 Correct 37 ms 25064 KB Output is correct
11 Correct 699 ms 50564 KB Output is correct
12 Correct 597 ms 25868 KB Output is correct
13 Correct 752 ms 50544 KB Output is correct
14 Correct 970 ms 50532 KB Output is correct
15 Correct 887 ms 50504 KB Output is correct
16 Correct 290 ms 25200 KB Output is correct
17 Correct 281 ms 25144 KB Output is correct
18 Correct 1427 ms 395320 KB Output is correct
19 Correct 1341 ms 395340 KB Output is correct
20 Correct 1850 ms 395208 KB Output is correct
21 Correct 942 ms 198212 KB Output is correct
22 Correct 368 ms 25252 KB Output is correct
23 Correct 329 ms 25276 KB Output is correct
24 Correct 1253 ms 395380 KB Output is correct