Submission #1019724

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019724		NoLove	Happiness (Balkan15_HAPPINESS)	C++14	40 / 100	361 ms	49232 KiB

happiness

/**
 *    author : Lăng Trọng Đạt
 *    created: 11-07-2024 
**/
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
// void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e18;
const int MOD = 1e9 + 7;

#define ll long long
const int MAXN = 1e7 + 5;
struct Node {
    ll sum, mx;
    Node *l, *r;
} st[MAXN];

int sz = 0, n;
void push(Node* v) {
    if (v->l == nullptr) {
        v->l = &st[++sz];
        v->r = &st[++sz];
    }
}
void add(int val, int event, Node *v = &st[0], int l = 1, int r = n) {
    if (l > val or val > r) return;
    if (l == r) {
        v->sum += event * val;
        if (v->sum > 0) 
            v->mx = val;
        else v->mx = 0;
    } else {
        int mid = (l + r) / 2;
        push(v);
        add(val, event, v->l, l, mid);
        add(val, event, v->r, mid + 1, r);

        v->sum = v->l->sum + v->r->sum;
        v->mx = max(v->l->mx, v->r->mx - v->l->sum);
    }
}

int cnt1 = 0, cnt_total = 0;
bool init(int coinsCount, long long maxCoinSize, long long coins[]) {
    n = maxCoinSize;
    FOR(i, 0, coinsCount - 1) {
        cnt1 += coins[i] == 1;
        add(coins[i], 1);
    }
    db("fuck")
    cnt_total += coinsCount;
    return (st[0].mx <= 1 && cnt1 > 0) or cnt_total == 0;
}
bool is_happy(int event, int coinsCount, long long coins[]) {
    cnt_total += event * coinsCount;
    FOR(i, 0, coinsCount - 1) {
        add(coins[i], event);
        cnt1 += event * (coins[i] == 1);
    }
    return (st[0].mx <= 1 && cnt1 > 0) or cnt_total == 0;
}

Compilation message (stderr)

happiness.cpp:22:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   22 | const int INF = 1e18;
      |                 ^~~~
happiness.cpp: In function 'bool init(int, long long int, long long int*)':
happiness.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
happiness.cpp:60:5: note: in expansion of macro 'FOR'
   60 |     FOR(i, 0, coinsCount - 1) {
      |     ^~~
happiness.cpp: In function 'bool is_happy(int, int, long long int*)':
happiness.cpp:18:31: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   18 | #define FOR(i, a, b) for (int (i) = a; (i) <= (b); i++)
      |                               ^
happiness.cpp:70:5: note: in expansion of macro 'FOR'
   70 |     FOR(i, 0, coinsCount - 1) {
      |     ^~~
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 / 10
• Subtask 2: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40