Submission #1114020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114020		asli_bg	Happiness (Balkan15_HAPPINESS)	C++11	100 / 100	1322 ms	380288 KiB

happiness

#include <bits/stdc++.h>
using namespace std;

#include "happiness.h"

//#define int long long

#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sp <<' '<<

#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)

#define cont(a) for(auto el:a) cout<<el<<' '; cout<<endl;
#define contp(a) for(auto el:a) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;

typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef long long ll;

#define endl '\n'

struct Dug{
    Dug *l,*r;
    //l--> sol çocuğum
    //r--> sag cocugum
    ll sum; //bas-son aralığının toplamı
    ll bas,son;

    Dug(ll bas,ll son) : l(nullptr) , r(nullptr), sum(0), bas(bas), son(son) {}
};

Dug *root;

void update(ll pos,ll val,Dug *nd){
    nd->sum+=val;
    ll bas=nd->bas;
    ll son=nd->son;
    if(bas==son) return; //leaf node
    
    ll mid=(bas+son)/2;

    //çocuklarım varsa
    if(pos<=mid){
        if(nd->l==nullptr) nd->l=new Dug(bas,mid);
        update(pos,val,nd->l);
    }
    else{
        if(nd->r==nullptr) nd->r=new Dug(mid+1,son);
        update(pos,val,nd->r);
    }
}

ll query(ll ql,ll qr,Dug *nd){
    ll bas=nd->bas;
    ll son=nd->son;

    if(ql>qr or bas>qr or son<ql) return 0;
    if(ql<=bas and son<=qr) return nd->sum;

    ll s1,s2;
    s1=s2=0;
    if(nd->l!=nullptr) s1=query(ql,qr,nd->l);
    if(nd->r!=nullptr) s2=query(ql,qr,nd->r);
    return s1+s2;
}

bool check(){
    ll cur=1;
    ll lim=root->sum;

    while(cur<=lim){
        ll top=query(1,cur,root);
        if(top<cur) return false;
        cur=top+1;
    }

    return true;
}

bool init(int n, long long m, long long coins[]) {

    root=new Dug(1,m);

    FOR(i,n) update(coins[i],coins[i],root);
    

	return check();
}

bool is_happy(int event, int n, long long coins[]) {
	FOR(i,n) update(coins[i],event*coins[i],root);
	return check();
}

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: 30 / 30
• Subtask 4: 40 / 40