oj.uz

Submission #427609

# Submission time Handle Problem Language Result Execution time Memory
427609 2021-06-14T17:48:42 Z CSQ31 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1559 ms 372248 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
	ll lf,rg,sum;
	node *l,*r;
	node(ll _lf,ll _rg){
		l = nullptr;
		r = nullptr;
		sum = 0;
		lf = _lf;
		rg = _rg;
	}
	void upd(ll val,ll c){
		sum+=val*c;
		if(lf==rg)return;
		ll tm = (lf+rg)/2;
		if(val<=tm){
			if(l == nullptr)l = new node(lf,tm);
			l->upd(val,c);
		}else{
			if(r == nullptr)r = new node(tm+1,rg);
			r->upd(val,c);
		}
	}
	long long query(long long a, long long b) {
		if (rg < a || lf > b) return 0;
		if (rg <= b && lf >= a) return sum;
		long long ret = 0;
		if (l) ret += l->query(a, b);
		if (r) ret += r->query(a, b);
		return ret;
	}
};
ll m;
node *root;
bool check(){
	ll cur = 1,mx = root->sum;
	while(cur<mx){
		ll t = root->query(1,cur);
		if(cur>t)return false;
		cur = t+1;
	}
	return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
    root = new node(1,m);	
	for(int i=0;i<coinsCount;i++)root->upd(coins[i],1);
	return check();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0;i<coinsCount;i++)root->upd(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 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 30 ms 13796 KB Output is correct
9 Correct 31 ms 14012 KB Output is correct
10 Correct 27 ms 13540 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 438 ms 34324 KB Output is correct
7 Correct 457 ms 33956 KB Output is correct
8 Correct 474 ms 34372 KB Output is correct
9 Correct 643 ms 44208 KB Output is correct
10 Correct 663 ms 48264 KB Output is correct
11 Correct 173 ms 33220 KB Output is correct
12 Correct 165 ms 33256 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1740 KB Output is correct
7 Correct 3 ms 1868 KB Output is correct
8 Correct 30 ms 13796 KB Output is correct
9 Correct 31 ms 14012 KB Output is correct
10 Correct 27 ms 13540 KB Output is correct
11 Correct 438 ms 34324 KB Output is correct
12 Correct 457 ms 33956 KB Output is correct
13 Correct 474 ms 34372 KB Output is correct
14 Correct 643 ms 44208 KB Output is correct
15 Correct 663 ms 48264 KB Output is correct
16 Correct 173 ms 33220 KB Output is correct
17 Correct 165 ms 33256 KB Output is correct
18 Correct 1038 ms 220348 KB Output is correct
19 Correct 1143 ms 229192 KB Output is correct
20 Correct 1559 ms 372248 KB Output is correct
21 Correct 838 ms 194148 KB Output is correct
22 Correct 214 ms 33220 KB Output is correct
23 Correct 230 ms 33232 KB Output is correct
24 Correct 1016 ms 211460 KB Output is correct