oj.uz

Submission #921656

# Submission time Handle Problem Language Result Execution time Memory
921656 2024-02-04T08:50:34 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
0 / 100
 51 ms 235164 KB 
#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;

    void init() {
        seg.assign((int)1e7,n1);
    }

    Node combine(Node l, Node r, int id1, int id2) {
        Node ret;

		ret.lIdx = id1;
		ret.rIdx = id2;
        
		ret.buildSum = l.buildSum + r.buildSum;
        ret.reqSum = l.reqSum;
		if (l.reqSum + l.buildSum + 1 < r.reqSum) {
			ret.reqSum = max(ret.reqSum, r.reqSum - 1 - l.buildSum);
		}
        return ret;
    }

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

    void inc(long long i, long long v, int x, long long lx, long long rx) {
        if (rx-lx==1) {
            seg[x].buildSum += v;
            return;
        }
        gen(x, rx-lx==2,lx);
        long long m=(lx+rx)>>1;
        if (i<m)inc(i,v,seg[x].lIdx,lx,m);
        else inc(i,v,seg[x].rIdx,m,rx);

        seg[x]=combine(seg[seg[x].lIdx], seg[seg[x].rIdx], seg[x].lIdx, seg[x].rIdx);
    }

    void add(long long i) {
        inc(i, i, 0, 0, n);
		// cout<<"add coin "<<i<<": "<<seg[0].buildSum<<"\n";
    }

    void sub(long long i) {
        inc(i, -i, 0, 0, n);
		// cout<<"remove coin "<<i<<": "<<seg[0].buildSum<<"\n";
    }

    bool happy() {
		// cout<<seg[0].reqSum<<"    "<<seg[0].buildSum<<"\n";;
        return seg[0].reqSum <= 0 || (seg[0].buildSum == 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 235164 KB Output is correct
2 Incorrect 51 ms 235088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 235164 KB Output is correct
2 Incorrect 51 ms 235088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 235164 KB Output is correct
2 Incorrect 51 ms 235088 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 235164 KB Output is correct
2 Incorrect 51 ms 235088 KB Output isn't correct
3 Halted 0 ms 0 KB -