oj.uz

답안 #921790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
921790 2024-02-04T10:19:25 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 772 ms 244016 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(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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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