제출 #921790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
921790		asdasdqwer	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	772 ms	244016 KiB

happiness

// #pragma GCC optimize("O3")
// #pragma GCC target("avx,avx2,sse4")

#include "happiness.h"
#include <vector>
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;
};

const long long n=((long long)1LL)<<40;
Node n1;
vector<Node> seg(10000000,n1);
int pt=0;
vector<int> st(100,0);
long long x,lx,rx;
int pp=-1;
int i=0;

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

inline void inc(long long i, long long v) {
	x=0;lx=0;rx=n;

	while (rx-lx!=1) {
		seg[x].buildSum += v;
		st[++pp]=x;
		long long m=(lx+rx)>>1;
		if (i<m) {
			rx=m;
			if (seg[x].lIdx == -1) {
				seg[x].lIdx = ++pt;
				if (rx-lx==1) seg[pt].reqSum = lx-1;
			}
			x=seg[x].lIdx;
		}

		else {
			lx=m;
			if (seg[x].rIdx == -1) {
				seg[x].rIdx = ++pt;
				if (rx-lx==1) seg[pt].reqSum = lx-1;
			}
			x=seg[x].rIdx;
		}
	}

	seg[x].buildSum += v;
	for (;pp>-1;--pp) {
		if (seg[st[pp]].lIdx == -1) {
			seg[st[pp]].reqSum = seg[seg[st[pp]].rIdx].reqSum;
		}

		else if (seg[st[pp]].rIdx == -1) {
			seg[st[pp]].reqSum = seg[seg[st[pp]].lIdx].reqSum;
		}

		else
			combine(seg[st[pp]], seg[seg[st[pp]].lIdx], seg[seg[st[pp]].rIdx]);
	}
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    for (i=0;i<coinsCount;++i) {
        inc(coins[i], coins[i]);
    }
    
	return seg[0].reqSum < 1;
}

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

    else {
        for (i=0;i<coinsCount;++i) {
            inc(coins[i], coins[i]);
        }
    }
    return seg[0].reqSum < 1;

}

컴파일 시 표준 에러 (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: 40 / 40