oj.uz

Submission #921730

# Submission time Handle Problem Language Result Execution time Memory
921730 2024-02-04T09:39:41 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524292 KB 
#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(12000000,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 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) {
	x=0;lx=0;rx=n;
	int pp=-1;

	while (rx-lx!=1) {
		seg[x].buildSum += v;
		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 (;pp>-1;--pp)
		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 183 ms 281992 KB Output is correct
2 Correct 201 ms 282012 KB Output is correct
3 Correct 116 ms 282200 KB Output is correct
4 Correct 122 ms 282192 KB Output is correct
5 Correct 126 ms 282196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 281992 KB Output is correct
2 Correct 201 ms 282012 KB Output is correct
3 Correct 116 ms 282200 KB Output is correct
4 Correct 122 ms 282192 KB Output is correct
5 Correct 126 ms 282196 KB Output is correct
6 Correct 103 ms 282204 KB Output is correct
7 Correct 104 ms 282136 KB Output is correct
8 Correct 112 ms 282340 KB Output is correct
9 Correct 105 ms 282448 KB Output is correct
10 Correct 111 ms 282284 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 281992 KB Output is correct
2 Correct 201 ms 282012 KB Output is correct
3 Correct 116 ms 282200 KB Output is correct
4 Correct 122 ms 282192 KB Output is correct
5 Correct 126 ms 282196 KB Output is correct
6 Correct 398 ms 286212 KB Output is correct
7 Correct 355 ms 285948 KB Output is correct
8 Correct 379 ms 286332 KB Output is correct
9 Correct 544 ms 287632 KB Output is correct
10 Correct 619 ms 287364 KB Output is correct
11 Correct 282 ms 286044 KB Output is correct
12 Correct 277 ms 286324 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 281992 KB Output is correct
2 Correct 201 ms 282012 KB Output is correct
3 Correct 116 ms 282200 KB Output is correct
4 Correct 122 ms 282192 KB Output is correct
5 Correct 126 ms 282196 KB Output is correct
6 Correct 103 ms 282204 KB Output is correct
7 Correct 104 ms 282136 KB Output is correct
8 Correct 112 ms 282340 KB Output is correct
9 Correct 105 ms 282448 KB Output is correct
10 Correct 111 ms 282284 KB Output is correct
11 Correct 398 ms 286212 KB Output is correct
12 Correct 355 ms 285948 KB Output is correct
13 Correct 379 ms 286332 KB Output is correct
14 Correct 544 ms 287632 KB Output is correct
15 Correct 619 ms 287364 KB Output is correct
16 Correct 282 ms 286044 KB Output is correct
17 Correct 277 ms 286324 KB Output is correct
18 Correct 613 ms 288440 KB Output is correct
19 Correct 575 ms 288496 KB Output is correct
20 Execution timed out 3378 ms 524292 KB Time limit exceeded
21 Halted 0 ms 0 KB -