Submission #1177050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177050		InvMOD	Happiness (Balkan15_HAPPINESS)	C++20	100 / 100	1082 ms	251640 KiB

happiness

#include<bits/stdc++.h>

//#define name "InvMOD"
#ifndef name
    #include "happiness.h"
#endif // name

using namespace std;

using ll = long long;

struct Node{
    ll sum;
    Node *left, *right;

    Node(ll v = 0): sum(v){
        left = nullptr;
        right = nullptr;
    }

    void update(ll l, ll r, ll x, ll val){
        if(l == r){
            sum += val;
        }
        else{
            ll m = l+r>>1;
            if(x <= m){
                if(!left) left = new Node();
                left->update(l, m, x, val);
            }
            else{
                if(!right) right = new Node();
                right->update(m + 1, r, x, val);
            }
            sum = (left != nullptr ? left->sum : 0) + (right != nullptr ? right->sum : 0);
        }
    }

    ll query(ll l, ll r, ll u, ll v){
        if(l >= u && r <= v){
            return sum;
        }
        ll m = l+r>>1;

        if(!left) left = new Node();
        if(!right) right = new Node();

        return (u <= m ? left->query(l, m, u, v) : 0) + (v > m ? right->query(m + 1, r, u, v) : 0);
    }
};

ll CoinSum, MxSize; Node st;

// if it's true then the sum will at least * 2 so its lg(1e12)
bool check(){
    ll x = 1;
    while(x < min(CoinSum, MxSize)){
        ll val = st.query(0, MxSize, 0, x);
        if(val < x) return false;

        x = val + 1;
    }
    return true;
}

bool init(int coinsCount, ll maxCoinSize, ll coins[]){
    MxSize = maxCoinSize;

    CoinSum = 0;
    for(int i = 0; i < coinsCount; i++){
        st.update(0, MxSize, coins[i], coins[i]);
        CoinSum += coins[i];
    }
    return check();
}

bool is_happy(int event, int coinsCount, ll coins[]){
    for(int i = 0; i < coinsCount; i++){
        st.update(0, MxSize, coins[i], 1ll * event * coins[i]);
        CoinSum += 1ll * event * coins[i];
    }
    return check();
}

#ifdef name
    int32_t main(){
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);

        int n,M; cin >> n >> M;

        ll coin1[n];
        for(int i = 0; i < n; i++){
            cin >> coin1[i];
        }
        cout << init(n, M, coin1) << "\n";

        int q; cin >> q;
        while(q--){
            int ev, cnt; cin >> ev >> cnt;

            ll coin2[cnt];
            for(int i = 0; i < cnt; i++){
                cin >> coin2[i];
            }

            cout << is_happy(ev, cnt, coin2) << "\n";
        }

        return 0;
    }

#endif // name

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