oj.uz

Submission #921717

# Submission time Handle Problem Language Result Execution time Memory
921717 2024-02-04T09:23:56 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524292 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#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 70 ms 282196 KB Output is correct
2 Correct 72 ms 282196 KB Output is correct
3 Correct 69 ms 282196 KB Output is correct
4 Correct 64 ms 282064 KB Output is correct
5 Correct 65 ms 282196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 282196 KB Output is correct
2 Correct 72 ms 282196 KB Output is correct
3 Correct 69 ms 282196 KB Output is correct
4 Correct 64 ms 282064 KB Output is correct
5 Correct 65 ms 282196 KB Output is correct
6 Correct 65 ms 282240 KB Output is correct
7 Correct 65 ms 282192 KB Output is correct
8 Correct 75 ms 282324 KB Output is correct
9 Correct 74 ms 282436 KB Output is correct
10 Correct 77 ms 282420 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 282196 KB Output is correct
2 Correct 72 ms 282196 KB Output is correct
3 Correct 69 ms 282196 KB Output is correct
4 Correct 64 ms 282064 KB Output is correct
5 Correct 65 ms 282196 KB Output is correct
6 Correct 310 ms 286240 KB Output is correct
7 Correct 304 ms 286112 KB Output is correct
8 Correct 315 ms 286332 KB Output is correct
9 Correct 472 ms 287500 KB Output is correct
10 Correct 507 ms 287656 KB Output is correct
11 Correct 275 ms 286316 KB Output is correct
12 Correct 268 ms 286036 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 282196 KB Output is correct
2 Correct 72 ms 282196 KB Output is correct
3 Correct 69 ms 282196 KB Output is correct
4 Correct 64 ms 282064 KB Output is correct
5 Correct 65 ms 282196 KB Output is correct
6 Correct 65 ms 282240 KB Output is correct
7 Correct 65 ms 282192 KB Output is correct
8 Correct 75 ms 282324 KB Output is correct
9 Correct 74 ms 282436 KB Output is correct
10 Correct 77 ms 282420 KB Output is correct
11 Correct 310 ms 286240 KB Output is correct
12 Correct 304 ms 286112 KB Output is correct
13 Correct 315 ms 286332 KB Output is correct
14 Correct 472 ms 287500 KB Output is correct
15 Correct 507 ms 287656 KB Output is correct
16 Correct 275 ms 286316 KB Output is correct
17 Correct 268 ms 286036 KB Output is correct
18 Correct 556 ms 288868 KB Output is correct
19 Correct 539 ms 288500 KB Output is correct
20 Execution timed out 3133 ms 524292 KB Time limit exceeded
21 Halted 0 ms 0 KB -