oj.uz

Submission #921712

# Submission time Handle Problem Language Result Execution time Memory
921712 2024-02-04T09:19:40 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 <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((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>-1;--i)
		combine(seg[st[i]], seg[seg[st[i]].lIdx], seg[seg[st[i]].rIdx]);
}

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


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

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 happy();
}

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 122 ms 282000 KB Output is correct
2 Correct 117 ms 282188 KB Output is correct
3 Correct 105 ms 282196 KB Output is correct
4 Correct 98 ms 282064 KB Output is correct
5 Correct 105 ms 282036 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 282000 KB Output is correct
2 Correct 117 ms 282188 KB Output is correct
3 Correct 105 ms 282196 KB Output is correct
4 Correct 98 ms 282064 KB Output is correct
5 Correct 105 ms 282036 KB Output is correct
6 Correct 94 ms 282112 KB Output is correct
7 Correct 94 ms 282192 KB Output is correct
8 Correct 124 ms 282264 KB Output is correct
9 Correct 112 ms 282420 KB Output is correct
10 Correct 98 ms 282452 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 282000 KB Output is correct
2 Correct 117 ms 282188 KB Output is correct
3 Correct 105 ms 282196 KB Output is correct
4 Correct 98 ms 282064 KB Output is correct
5 Correct 105 ms 282036 KB Output is correct
6 Correct 323 ms 286232 KB Output is correct
7 Correct 329 ms 286288 KB Output is correct
8 Correct 370 ms 285732 KB Output is correct
9 Correct 485 ms 286396 KB Output is correct
10 Correct 504 ms 286804 KB Output is correct
11 Correct 278 ms 286032 KB Output is correct
12 Correct 276 ms 285776 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 282000 KB Output is correct
2 Correct 117 ms 282188 KB Output is correct
3 Correct 105 ms 282196 KB Output is correct
4 Correct 98 ms 282064 KB Output is correct
5 Correct 105 ms 282036 KB Output is correct
6 Correct 94 ms 282112 KB Output is correct
7 Correct 94 ms 282192 KB Output is correct
8 Correct 124 ms 282264 KB Output is correct
9 Correct 112 ms 282420 KB Output is correct
10 Correct 98 ms 282452 KB Output is correct
11 Correct 323 ms 286232 KB Output is correct
12 Correct 329 ms 286288 KB Output is correct
13 Correct 370 ms 285732 KB Output is correct
14 Correct 485 ms 286396 KB Output is correct
15 Correct 504 ms 286804 KB Output is correct
16 Correct 278 ms 286032 KB Output is correct
17 Correct 276 ms 285776 KB Output is correct
18 Correct 590 ms 288284 KB Output is correct
19 Correct 602 ms 288592 KB Output is correct
20 Execution timed out 2155 ms 524292 KB Time limit exceeded
21 Halted 0 ms 0 KB -