Submission #1208283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208283		goulthen	Happiness (Balkan15_HAPPINESS)	C++20	0 / 100	0 ms	320 KiB

happiness

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

#define ll long long
#define rep(i, a, b) for (int i = a; i <= b; ++i)
#define per(i, b, a) for (int i = b; i >= a; --i)

const long long INF = 1e18 + 5;

struct Node {
    array<int,2> v = {0,1};
    Node *l = nullptr;
    Node *r = nullptr;
};
 
struct Seg3 {
    Node *root = new Node;

    void apply(Node *cur, ll x, bool ch = 0) {
        (cur->v)[0] += x;
        if (ch) (cur->v)[1] += x;
        else (cur->v)[1] -= x;
        //cout << x << ' ' <<(cur->v)[1] << '\n';
    }

    array<int,2> join(array<int,2> a, array<int,2> b) {
        return {a[0] + b[0], min(a[1], b[1] + a[0])};
    }

    void update(Node *cur, ll l, ll r, ll ti, ll x, bool flag = 0) {
        if (ti < l || ti > r) return;
        if (l>=ti && r <= ti) {
            apply(cur, x, flag);
            return;
        }
        ll mid =(l+r)>>1;

        if (!cur->l) cur->l = new Node;
    	if (!cur->r) cur->r = new Node;

        update((cur->l),l,mid,ti,x);
        update((cur->r),mid+1,r,ti,x);
        (cur->v) = join((cur->l)->v,(cur->r)->v);
    }
    array<int,2> query(Node *cur, ll l, ll r, ll tl, ll tr) {
    	if(!cur) return {0,1};
        if (tr < l || tl > r) return {0,1};
        if (l >= tl && r <= tr) return (cur-> v);
        ll mid = (l+r)>>1;
        return join(query((cur->l), l, mid, tl,tr), query((cur->r),mid+1,r, tl,tr));
    }
} seg;

ll s = 0, m;
map<ll,ll> mp;

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
	m = maxCoinSize;
	rep(i,0,coinsCount-1) {
		ll x = coins[i];
        s+=x;
        mp[x]++;
        seg.update(seg.root,1,m,x,x,(mp[x]==1));
    }
    if (s == 0) return 1;
	
	ll mn = seg.query(seg.root,1,m,1,min(m,s))[1];
    return (mp[1]>0 && mn >= 0);
}

bool is_happy(int event, int coinsCount, long long coins[]) {
    rep(i,0,coinsCount-1) {
		ll x = coins[i];
        s += x*event;
        mp[x]+=event;
        seg.update(seg.root,1,m,x,x*event,(mp[x]==1 && event == 1));
    }
    if (s == 0) return 1;

    ll mn = seg.query(seg.root,1,m,1,min(m,s))[1];
	

    return (mp[1]>0 && mn >= 0);
}

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