oj.uz

Submission #284064

# Submission time Handle Problem Language Result Execution time Memory
284064 2020-08-26T16:03:50 Z NaimSS Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1659 ms 256760 KB 
#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;

const ll inf = 1e16;
const ll MAX = (1e12) + 10;
struct node{
  node* c[2];
  ll sum;
  node(){c[0] = c[1] = nullptr;sum = 0;}
  
  void upd(ll p,ll v,ll i = 0, ll j = MAX){
  	if(i == j){
  		sum+=v;
  		return;
  	}
  	ll m = (i + j)/2;
  	if(p<=m){
  		if(!c[0])c[0] = new node();
  		c[0]->upd(p,v,i,m);
  	}else{
  		if(!c[1])c[1] = new node();
  		c[1]->upd(p,v,m+1,j);
  	}
  	sum=(c[0] ? c[0]->sum : 0) + (c[1] ? c[1]->sum : 0);
  }
  ll query(ll a,ll b,ll i = 0,ll j = MAX){
  	if(i > j || i > b || j < a)return 0;
  	if(a<=i and j<=b)return sum;
  	ll m = (i + j)/2;
  	return (c[0] ? c[0]->query(a,b,i,m) : 0) + (c[1] ? c[1]->query(a,b,m+1,j) : 0);
  }
  	
};

node* tree;
ll tot=0;
ll mx = 0;
bool good(){
	ll have = 0;
	while(have < min(mx,tot)){
		ll novo = tree->query(0,have + 1);
		if(novo == have)return 0;
		have = novo;
	}
	return 1;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	tree = new node();
	mx = maxCoinSize;
	tot=0;
	for(int i=0;i<coinsCount;i++){
		ll v = coins[i];
		tree->upd(v,v);
		tot+=v;
	}
	return good();
}
bool is_happy(int event, int coinsCount, long long coins[]) {
	for(int i=0;i<coinsCount;i++){
		ll v = coins[i];
		tree->upd(v,v*event);
		tot+=v*event;
	}
	return good();
}

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 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 1408 KB Output is correct
7 Correct 4 ms 1408 KB Output is correct
8 Correct 31 ms 9464 KB Output is correct
9 Correct 32 ms 9464 KB Output is correct
10 Correct 29 ms 9216 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 683 ms 25748 KB Output is correct
7 Correct 708 ms 26360 KB Output is correct
8 Correct 794 ms 26608 KB Output is correct
9 Correct 993 ms 34556 KB Output is correct
10 Correct 970 ms 37240 KB Output is correct
11 Correct 311 ms 26188 KB Output is correct
12 Correct 317 ms 26324 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 1408 KB Output is correct
7 Correct 4 ms 1408 KB Output is correct
8 Correct 31 ms 9464 KB Output is correct
9 Correct 32 ms 9464 KB Output is correct
10 Correct 29 ms 9216 KB Output is correct
11 Correct 683 ms 25748 KB Output is correct
12 Correct 708 ms 26360 KB Output is correct
13 Correct 794 ms 26608 KB Output is correct
14 Correct 993 ms 34556 KB Output is correct
15 Correct 970 ms 37240 KB Output is correct
16 Correct 311 ms 26188 KB Output is correct
17 Correct 317 ms 26324 KB Output is correct
18 Correct 1203 ms 152952 KB Output is correct
19 Correct 1267 ms 158972 KB Output is correct
20 Correct 1659 ms 256760 KB Output is correct
21 Correct 882 ms 135028 KB Output is correct
22 Correct 327 ms 28280 KB Output is correct
23 Correct 339 ms 28664 KB Output is correct
24 Correct 1114 ms 146852 KB Output is correct