Submission #736267

#	Time	Username	Problem	Language	Result	Execution time	Memory
736267		Dan4Life	Happiness (Balkan15_HAPPINESS)	C++17	30 / 100	519 ms	31176 KiB

happiness

#include "happiness.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mxN = (int)2e5+10;
ll mx, segTree[mxN*4];
int L[mxN*4], R[mxN*4];
int IND = 1;

void upd(ll x, ll v, int p=1, ll l=1, ll r=mx){
	if(l==r){ segTree[p]+=v; return; }
	ll mid = (l+r)/2;
	if(x<=mid){
		if(!L[p]) L[p]=++IND;
		upd(x,v,L[p],l,mid);
	}
	else{
		if(!R[p]) R[p]=++IND;
		upd(x,v,R[p],mid+1,r);
	}
	segTree[p]= segTree[L[p]]+segTree[R[p]];
}

ll query(ll i, ll j, int p=1, ll l=1, ll r=mx){
	if(i>r or j<l or i>j or !p) return 0;
	if(i<=l and r<=j) return segTree[p];
	ll mid = (l+r)/2;
	return query(i,j,L[p],l,mid)+query(i,j,R[p],mid+1,r);
}

bool chk(){
    ll coin = 1, tot = query(1,mx);
    while(coin<=mx){
        ll sum = query(1,coin);
        if(sum+1>mx) return true;
        if(tot==sum) return true;
        if(query(coin+1,sum+1)==0) return false;
        coin = sum+1;
    }
    return true;
}

bool init(int n, ll M, ll a[]) {
    mx = M;
    for(int i = 0; i < n; i++) upd(a[i],a[i]);
	return chk();
}

bool is_happy(int e, int n, ll a[]) {
    for(int i = 0; i < n; i++) upd(a[i],a[i]*e);
	return chk();
}

Compilation message (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40