Submission #921699

#	Time	Username	Problem	Language	Result	Execution time	Memory
921699		asdasdqwer	Happiness (Balkan15_HAPPINESS)	C++14	60 / 100	3091 ms	524288 KiB

happiness

#pragma GCC optimize("O3")

#include "happiness.h"

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

struct Node {
    // sum that is required such that the first element of the subarray is chosen
    long long reqSum = 0;

    // sum of all elements in the subarray
    long long buildSum = 0;

    // index of left and right children
    int lIdx = -1, rIdx = -1;
};

struct Segtree {
    const long long n=((long long)1LL)<<40;
    Node n1;
    vector<Node> seg;
    int pt=0;
	vector<int> st;

    void init() {
        seg.assign((int)1e7 + 2*(int)1e6,n1);
		st.assign(100,0);
    }

    inline void combine(Node &ret, Node &l, Node &r) {        
		ret.buildSum = l.buildSum + r.buildSum;
		ret.reqSum = l.reqSum;
		if (r.buildSum != 0)
        	ret.reqSum = max(l.reqSum, r.reqSum - l.buildSum);
    }

    inline void gen(int x, bool two, long long f) {
        if (seg[x].lIdx != -1) return;
        seg[x].lIdx = ++pt;
        if (two) {
            seg[pt].reqSum = f-1;
        }

        seg[x].rIdx = ++pt;
        if (two) {
            seg[pt].reqSum = f;
        }
    }

    inline void inc(long long i, long long v) {
		int x=0;
		long long lx = 0;
		long long rx = n;
		int pp=-1;
		while (rx-lx!=1) {
			st[++pp]=x;
			gen(x,rx-lx==2,lx);
			long long m=(lx+rx)>>1;
			if (i<m) rx=m, x=seg[x].lIdx;
			else     lx=m, x=seg[x].rIdx;
		}

		seg[x].buildSum += v;
		for (int i=pp;i>=0;i--)
			combine(seg[st[i]], seg[seg[st[i]].lIdx], seg[seg[st[i]].rIdx]);
    }

    void add(long long i) {
        inc(i, i);
    }

    void sub(long long i) {
        inc(i, -i);
    }

    bool happy() {
        return seg[0].reqSum <= 0;
    }
};

Segtree sg;

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    sg.init();
    for (int i=0;i<coinsCount;i++) {
        sg.add(coins[i]);
    }
    return sg.happy();
}

bool is_happy(int event, int32_t coinsCount, long long coins[]) {
    if (event == -1) {
        for (int i=0;i<coinsCount;i++) {
            sg.sub(coins[i]);
        }
    }

    else {
        for (int i=0;i<coinsCount;i++) {
            sg.add(coins[i]);
        }
    }
    
    return sg.happy();
}

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