oj.uz

Submission #921699

# Submission time Handle Problem Language Result Execution time Memory
921699 2024-02-04T09:11:54 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524288 KB 
#pragma GCC optimize("O3")

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

struct Segtree {
    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>=0;i--)
			combine(seg[st[i]], seg[seg[st[i]].lIdx], seg[seg[st[i]].rIdx]);
    }

    void add(long long i) {
        inc(i, i);
    }

    void sub(long long i) {
        inc(i, -i);
    }

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

Segtree sg;

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

bool is_happy(int event, int32_t coinsCount, long long coins[]) {
    if (event == -1) {
        for (int i=0;i<coinsCount;i++) {
            sg.sub(coins[i]);
        }
    }

    else {
        for (int i=0;i<coinsCount;i++) {
            sg.add(coins[i]);
        }
    }
    
    return sg.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 79 ms 282192 KB Output is correct
2 Correct 80 ms 282080 KB Output is correct
3 Correct 81 ms 282196 KB Output is correct
4 Correct 79 ms 282192 KB Output is correct
5 Correct 78 ms 282192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 282192 KB Output is correct
2 Correct 80 ms 282080 KB Output is correct
3 Correct 81 ms 282196 KB Output is correct
4 Correct 79 ms 282192 KB Output is correct
5 Correct 78 ms 282192 KB Output is correct
6 Correct 79 ms 282192 KB Output is correct
7 Correct 80 ms 282196 KB Output is correct
8 Correct 91 ms 282448 KB Output is correct
9 Correct 95 ms 282456 KB Output is correct
10 Correct 87 ms 282448 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 282192 KB Output is correct
2 Correct 80 ms 282080 KB Output is correct
3 Correct 81 ms 282196 KB Output is correct
4 Correct 79 ms 282192 KB Output is correct
5 Correct 78 ms 282192 KB Output is correct
6 Correct 390 ms 286188 KB Output is correct
7 Correct 319 ms 286292 KB Output is correct
8 Correct 366 ms 286108 KB Output is correct
9 Correct 474 ms 287892 KB Output is correct
10 Correct 493 ms 287512 KB Output is correct
11 Correct 285 ms 286160 KB Output is correct
12 Correct 268 ms 286256 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 282192 KB Output is correct
2 Correct 80 ms 282080 KB Output is correct
3 Correct 81 ms 282196 KB Output is correct
4 Correct 79 ms 282192 KB Output is correct
5 Correct 78 ms 282192 KB Output is correct
6 Correct 79 ms 282192 KB Output is correct
7 Correct 80 ms 282196 KB Output is correct
8 Correct 91 ms 282448 KB Output is correct
9 Correct 95 ms 282456 KB Output is correct
10 Correct 87 ms 282448 KB Output is correct
11 Correct 390 ms 286188 KB Output is correct
12 Correct 319 ms 286292 KB Output is correct
13 Correct 366 ms 286108 KB Output is correct
14 Correct 474 ms 287892 KB Output is correct
15 Correct 493 ms 287512 KB Output is correct
16 Correct 285 ms 286160 KB Output is correct
17 Correct 268 ms 286256 KB Output is correct
18 Correct 549 ms 288832 KB Output is correct
19 Correct 611 ms 288596 KB Output is correct
20 Execution timed out 3091 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -