oj.uz

Submission #921675

# Submission time Handle Problem Language Result Execution time Memory
921675 2024-02-04T08:57:43 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524292 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 + 2*(int)1e6,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 (r.buildSum != 0)
        	ret.reqSum = max(l.reqSum, r.reqSum - 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;
    }
};

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 93 ms 282288 KB Output is correct
2 Correct 91 ms 281992 KB Output is correct
3 Correct 95 ms 282168 KB Output is correct
4 Correct 92 ms 282108 KB Output is correct
5 Correct 91 ms 282200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 282288 KB Output is correct
2 Correct 91 ms 281992 KB Output is correct
3 Correct 95 ms 282168 KB Output is correct
4 Correct 92 ms 282108 KB Output is correct
5 Correct 91 ms 282200 KB Output is correct
6 Correct 91 ms 282200 KB Output is correct
7 Correct 94 ms 282192 KB Output is correct
8 Correct 99 ms 282284 KB Output is correct
9 Correct 102 ms 282452 KB Output is correct
10 Correct 110 ms 282480 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 282288 KB Output is correct
2 Correct 91 ms 281992 KB Output is correct
3 Correct 95 ms 282168 KB Output is correct
4 Correct 92 ms 282108 KB Output is correct
5 Correct 91 ms 282200 KB Output is correct
6 Correct 397 ms 284992 KB Output is correct
7 Correct 402 ms 284752 KB Output is correct
8 Correct 457 ms 284976 KB Output is correct
9 Correct 603 ms 285928 KB Output is correct
10 Correct 603 ms 285524 KB Output is correct
11 Correct 304 ms 284464 KB Output is correct
12 Correct 284 ms 284408 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 282288 KB Output is correct
2 Correct 91 ms 281992 KB Output is correct
3 Correct 95 ms 282168 KB Output is correct
4 Correct 92 ms 282108 KB Output is correct
5 Correct 91 ms 282200 KB Output is correct
6 Correct 91 ms 282200 KB Output is correct
7 Correct 94 ms 282192 KB Output is correct
8 Correct 99 ms 282284 KB Output is correct
9 Correct 102 ms 282452 KB Output is correct
10 Correct 110 ms 282480 KB Output is correct
11 Correct 397 ms 284992 KB Output is correct
12 Correct 402 ms 284752 KB Output is correct
13 Correct 457 ms 284976 KB Output is correct
14 Correct 603 ms 285928 KB Output is correct
15 Correct 603 ms 285524 KB Output is correct
16 Correct 304 ms 284464 KB Output is correct
17 Correct 284 ms 284408 KB Output is correct
18 Correct 595 ms 286180 KB Output is correct
19 Correct 599 ms 286276 KB Output is correct
20 Execution timed out 3072 ms 524292 KB Time limit exceeded
21 Halted 0 ms 0 KB -