Submission #921790

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
921790	2024-02-04T10:19:25 Z	asdasdqwer	Happiness (Balkan15_HAPPINESS)	C++14	100 / 100	772 ms	244016 KB

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;

}

Compilation message

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	235092 KB	Output is correct
2	Correct	42 ms	235264 KB	Output is correct
3	Correct	41 ms	235092 KB	Output is correct
4	Correct	41 ms	235200 KB	Output is correct
5	Correct	41 ms	235092 KB	Output is correct

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	235092 KB	Output is correct
2	Correct	42 ms	235264 KB	Output is correct
3	Correct	41 ms	235092 KB	Output is correct
4	Correct	41 ms	235200 KB	Output is correct
5	Correct	41 ms	235092 KB	Output is correct
6	Correct	41 ms	235092 KB	Output is correct
7	Correct	41 ms	235256 KB	Output is correct
8	Correct	49 ms	235288 KB	Output is correct
9	Correct	56 ms	235344 KB	Output is correct
10	Correct	48 ms	235348 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	235092 KB	Output is correct
2	Correct	42 ms	235264 KB	Output is correct
3	Correct	41 ms	235092 KB	Output is correct
4	Correct	41 ms	235200 KB	Output is correct
5	Correct	41 ms	235092 KB	Output is correct
6	Correct	268 ms	239460 KB	Output is correct
7	Correct	254 ms	239136 KB	Output is correct
8	Correct	242 ms	239264 KB	Output is correct
9	Correct	391 ms	240876 KB	Output is correct
10	Correct	424 ms	240512 KB	Output is correct
11	Correct	221 ms	239132 KB	Output is correct
12	Correct	224 ms	239260 KB	Output is correct

Subtask #4

40.0 / 40.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	235092 KB	Output is correct
2	Correct	42 ms	235264 KB	Output is correct
3	Correct	41 ms	235092 KB	Output is correct
4	Correct	41 ms	235200 KB	Output is correct
5	Correct	41 ms	235092 KB	Output is correct
6	Correct	41 ms	235092 KB	Output is correct
7	Correct	41 ms	235256 KB	Output is correct
8	Correct	49 ms	235288 KB	Output is correct
9	Correct	56 ms	235344 KB	Output is correct
10	Correct	48 ms	235348 KB	Output is correct
11	Correct	268 ms	239460 KB	Output is correct
12	Correct	254 ms	239136 KB	Output is correct
13	Correct	242 ms	239264 KB	Output is correct
14	Correct	391 ms	240876 KB	Output is correct
15	Correct	424 ms	240512 KB	Output is correct
16	Correct	221 ms	239132 KB	Output is correct
17	Correct	224 ms	239260 KB	Output is correct
18	Correct	489 ms	241556 KB	Output is correct
19	Correct	507 ms	241488 KB	Output is correct
20	Correct	772 ms	244016 KB	Output is correct
21	Correct	434 ms	241144 KB	Output is correct
22	Correct	237 ms	241228 KB	Output is correct
23	Correct	254 ms	242004 KB	Output is correct
24	Correct	426 ms	241488 KB	Output is correct