Submission #931849

#	Time	Username	Problem	Language	Result	Execution time	Memory
931849		dead0ne	Happiness (Balkan15_HAPPINESS)	C++17	60 / 100	1029 ms	524288 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 spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007
#define MX 300005
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);
}

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: 0 / 40