Submission #381658

#	Time	Username	Problem	Language	Result	Execution time	Memory
381658		ntabc05101	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	1520 ms	380388 KiB

happiness

#include "happiness.h"
#include<bits/stdc++.h>

#define LL long long

struct Node {
        LL l, r, value;
        Node *lc, *rc;

        Node(LL L, LL R): l(L), r(R), value(0), lc(nullptr), rc(nullptr) {};

        void update(LL p, LL delta) {
                value+=delta;
                if (l!=r) {
                        LL mid=l+r>>1;
                        if (p>mid) {
                                if (!rc) rc=new Node(mid+1, r);
                                rc->update(p, delta);
                        }
                        else {
                                if (!lc) lc=new Node(l, mid);
                                lc->update(p, delta);
                        }
                }
        }

        LL get(LL left, LL right) {
                if (left>r or right<l) return 0;
                if (left<=l and right>=r) return value;

                LL ret=0;
                if (lc) ret+=lc->get(left, right);
                if (rc) ret+=rc->get(left, right);
                return ret;
        }
};

Node* root;

bool check() {
        LL current=0, sum=root->value;
        while (current<sum) {
                LL t=root->get(1, current);
                if (t<current) return false;
                current=t+1;
        }

        return true;
}

bool init(int coinsCount, LL maxCoinSize, LL coins[]) {
        root=new Node(1, maxCoinSize);
        for (int i=0; i<coinsCount; i++) {
                root->update(coins[i], coins[i]);
        }

        return check();
}

bool is_happy(int event, int coinsCount, LL coins[]) {
        for (int i=0; i<coinsCount; i++) {
                root->update(coins[i], event*coins[i]);
        }

        return check();
}

/*int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n; LL m; std::cin>>n>>m;
        LL coins[n];
        for (int i=0; i<n; i++) std::cin>>coins[i];
        std::cout<<init(n, m, coins)<<"\n";

        int q; std::cin>>q;
        while (q--) {
                int e, k; std::cin>>e>>k;
                LL coins[k]; 
                for (int i=0; i<k; i++) std::cin>>coins[i];
                std::cout<<is_happy(e, k, coins)<<"\n";
        }

        return 0;
}*/

Compilation message (stderr)

happiness.cpp: In member function 'void Node::update(long long int, long long int)':
happiness.cpp:15:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |                         LL mid=l+r>>1;
      |                                ~^~
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