oj.uz

Submission #921725

# Submission time Handle Problem Language Result Execution time Memory
921725 2024-02-04T09:33:12 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1657 ms 524288 KB 
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,sse4")

#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;
};

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

void init() {
	seg.assign(11000000,n1);
	st.assign(100,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) {
	int x=0;
	long long lx = 0;
	long long 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 (int i=pp;i>-1;--i)
		combine(seg[st[i]], seg[seg[st[i]].lIdx], seg[seg[st[i]].rIdx]);
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    init();
    for (int 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 (int i=0;i<coinsCount;++i) {
            inc(coins[i], -coins[i]);
        }
    }

    else {
        for (int 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 53 ms 258728 KB Output is correct
2 Correct 49 ms 258692 KB Output is correct
3 Correct 50 ms 258652 KB Output is correct
4 Correct 50 ms 258532 KB Output is correct
5 Correct 51 ms 258644 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 258728 KB Output is correct
2 Correct 49 ms 258692 KB Output is correct
3 Correct 50 ms 258652 KB Output is correct
4 Correct 50 ms 258532 KB Output is correct
5 Correct 51 ms 258644 KB Output is correct
6 Correct 54 ms 258640 KB Output is correct
7 Correct 52 ms 258644 KB Output is correct
8 Correct 61 ms 258896 KB Output is correct
9 Correct 58 ms 258944 KB Output is correct
10 Correct 57 ms 258996 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 258728 KB Output is correct
2 Correct 49 ms 258692 KB Output is correct
3 Correct 50 ms 258652 KB Output is correct
4 Correct 50 ms 258532 KB Output is correct
5 Correct 51 ms 258644 KB Output is correct
6 Correct 317 ms 262736 KB Output is correct
7 Correct 269 ms 262740 KB Output is correct
8 Correct 297 ms 262936 KB Output is correct
9 Correct 477 ms 264016 KB Output is correct
10 Correct 454 ms 264184 KB Output is correct
11 Correct 245 ms 262676 KB Output is correct
12 Correct 238 ms 262612 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 258728 KB Output is correct
2 Correct 49 ms 258692 KB Output is correct
3 Correct 50 ms 258652 KB Output is correct
4 Correct 50 ms 258532 KB Output is correct
5 Correct 51 ms 258644 KB Output is correct
6 Correct 54 ms 258640 KB Output is correct
7 Correct 52 ms 258644 KB Output is correct
8 Correct 61 ms 258896 KB Output is correct
9 Correct 58 ms 258944 KB Output is correct
10 Correct 57 ms 258996 KB Output is correct
11 Correct 317 ms 262736 KB Output is correct
12 Correct 269 ms 262740 KB Output is correct
13 Correct 297 ms 262936 KB Output is correct
14 Correct 477 ms 264016 KB Output is correct
15 Correct 454 ms 264184 KB Output is correct
16 Correct 245 ms 262676 KB Output is correct
17 Correct 238 ms 262612 KB Output is correct
18 Correct 516 ms 265440 KB Output is correct
19 Correct 523 ms 265044 KB Output is correct
20 Runtime error 1657 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -