oj.uz

Submission #921671

# Submission time Handle Problem Language Result Execution time Memory
921671 2024-02-04T08:56:41 Z asdasdqwer Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 743 ms 482776 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 (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 76 ms 235180 KB Output is correct
2 Correct 75 ms 235116 KB Output is correct
3 Correct 89 ms 235088 KB Output is correct
4 Correct 83 ms 235224 KB Output is correct
5 Correct 83 ms 235088 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 235180 KB Output is correct
2 Correct 75 ms 235116 KB Output is correct
3 Correct 89 ms 235088 KB Output is correct
4 Correct 83 ms 235224 KB Output is correct
5 Correct 83 ms 235088 KB Output is correct
6 Correct 77 ms 235092 KB Output is correct
7 Correct 82 ms 235116 KB Output is correct
8 Correct 91 ms 235364 KB Output is correct
9 Correct 95 ms 235512 KB Output is correct
10 Correct 86 ms 235344 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 235180 KB Output is correct
2 Correct 75 ms 235116 KB Output is correct
3 Correct 89 ms 235088 KB Output is correct
4 Correct 83 ms 235224 KB Output is correct
5 Correct 83 ms 235088 KB Output is correct
6 Correct 392 ms 239296 KB Output is correct
7 Correct 353 ms 239108 KB Output is correct
8 Correct 390 ms 239440 KB Output is correct
9 Correct 618 ms 240724 KB Output is correct
10 Correct 644 ms 240468 KB Output is correct
11 Correct 354 ms 239116 KB Output is correct
12 Correct 303 ms 239172 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 235180 KB Output is correct
2 Correct 75 ms 235116 KB Output is correct
3 Correct 89 ms 235088 KB Output is correct
4 Correct 83 ms 235224 KB Output is correct
5 Correct 83 ms 235088 KB Output is correct
6 Correct 77 ms 235092 KB Output is correct
7 Correct 82 ms 235116 KB Output is correct
8 Correct 91 ms 235364 KB Output is correct
9 Correct 95 ms 235512 KB Output is correct
10 Correct 86 ms 235344 KB Output is correct
11 Correct 392 ms 239296 KB Output is correct
12 Correct 353 ms 239108 KB Output is correct
13 Correct 390 ms 239440 KB Output is correct
14 Correct 618 ms 240724 KB Output is correct
15 Correct 644 ms 240468 KB Output is correct
16 Correct 354 ms 239116 KB Output is correct
17 Correct 303 ms 239172 KB Output is correct
18 Correct 649 ms 241700 KB Output is correct
19 Correct 589 ms 241792 KB Output is correct
20 Runtime error 743 ms 482776 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -