oj.uz

Submission #921686

# Submission time Handle Problem Language Result Execution time Memory
921686 2024-02-04T09:02:03 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;

    void init() {
        seg.assign((int)1e7 + 2*(int)1e6,n1);
    }

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

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

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

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

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

    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 78 ms 282136 KB Output is correct
2 Correct 74 ms 282196 KB Output is correct
3 Correct 72 ms 282072 KB Output is correct
4 Correct 71 ms 282196 KB Output is correct
5 Correct 71 ms 282172 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 282136 KB Output is correct
2 Correct 74 ms 282196 KB Output is correct
3 Correct 72 ms 282072 KB Output is correct
4 Correct 71 ms 282196 KB Output is correct
5 Correct 71 ms 282172 KB Output is correct
6 Correct 70 ms 282196 KB Output is correct
7 Correct 72 ms 282196 KB Output is correct
8 Correct 77 ms 282456 KB Output is correct
9 Correct 81 ms 282272 KB Output is correct
10 Correct 76 ms 282448 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 282136 KB Output is correct
2 Correct 74 ms 282196 KB Output is correct
3 Correct 72 ms 282072 KB Output is correct
4 Correct 71 ms 282196 KB Output is correct
5 Correct 71 ms 282172 KB Output is correct
6 Correct 388 ms 285908 KB Output is correct
7 Correct 317 ms 285984 KB Output is correct
8 Correct 277 ms 285952 KB Output is correct
9 Correct 407 ms 287300 KB Output is correct
10 Correct 487 ms 287284 KB Output is correct
11 Correct 241 ms 285856 KB Output is correct
12 Correct 242 ms 285704 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 282136 KB Output is correct
2 Correct 74 ms 282196 KB Output is correct
3 Correct 72 ms 282072 KB Output is correct
4 Correct 71 ms 282196 KB Output is correct
5 Correct 71 ms 282172 KB Output is correct
6 Correct 70 ms 282196 KB Output is correct
7 Correct 72 ms 282196 KB Output is correct
8 Correct 77 ms 282456 KB Output is correct
9 Correct 81 ms 282272 KB Output is correct
10 Correct 76 ms 282448 KB Output is correct
11 Correct 388 ms 285908 KB Output is correct
12 Correct 317 ms 285984 KB Output is correct
13 Correct 277 ms 285952 KB Output is correct
14 Correct 407 ms 287300 KB Output is correct
15 Correct 487 ms 287284 KB Output is correct
16 Correct 241 ms 285856 KB Output is correct
17 Correct 242 ms 285704 KB Output is correct
18 Correct 504 ms 287976 KB Output is correct
19 Correct 524 ms 287864 KB Output is correct
20 Execution timed out 3082 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -