Submission #1145453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145453		Trisanu_Das	Happiness (Balkan15_HAPPINESS)	C++20	60 / 100	1163 ms	589824 KiB

happiness

#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#include "happiness.h"
#define pb push_back
#define mp make_pair
#define ll long long
using namespace std;

struct Node{
    ll sum=0, l, r;
    Node *lc = nullptr, *rc = nullptr;
    Node(ll l, ll r) : l(l), r(r) {}
    
    void extend(){
        if(!lc && l<r){
            ll m = (l+r)>>1;
            lc = new Node(l, m);
            rc = new Node(m+1, r);
        }
    }

    void add(ll tar, ll val){
        extend();
        sum += val;
        if(lc){
            if(tar <= lc->r) lc->add(tar, val);
            else rc->add(tar,val);
        }
    }

    ll query(ll ql, ll qr){
        if(ql<=l && r<=qr) return sum;
        if(l>qr || r<ql) return 0;
        extend();
        return lc->query(ql, qr) + rc->query(ql, qr);
    }
};

Node *root;

bool is_happy(int event, int coinsCount, long long coins[]){
    for(int i=0; i<coinsCount; i++) root->add(coins[i], coins[i] * event);
    ll x = 1;
    while(x <= root->sum){
        ll res = root->query(1, x);
        if(res < x) return false;
        x = res + 1;
    }
    return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    root = new Node(1, maxCoinSize);
    return is_happy(1, coinsCount, coins);
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40