oj.uz

Submission #1019774

# Submission time Handle Problem Language Result Execution time Memory
1019774 2024-07-11T08:44:23 Z NoLove Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 785 ms 481876 KB 
/**
 *    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 = 2e7 + 5;
struct Node {
    ll sum, mx;
    Node *l, *r;
} st[MAXN];

ll sz = 0, n;
void push(Node* v) {
    if (v->l == nullptr) {
        v->l = &st[++sz];
        v->r = &st[++sz];
    }
}

void add(ll val, ll event, Node *v = &st[0], ll l = 1, ll 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 {
        ll 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);
    }
}

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

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:61:5: note: in expansion of macro 'FOR'
   61 |     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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 2 ms 2248 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 18 ms 18020 KB Output is correct
9 Correct 17 ms 18268 KB Output is correct
10 Correct 16 ms 17500 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 189 ms 37216 KB Output is correct
7 Correct 191 ms 36948 KB Output is correct
8 Correct 185 ms 37244 KB Output is correct
9 Correct 272 ms 46416 KB Output is correct
10 Correct 318 ms 49492 KB Output is correct
11 Correct 118 ms 26192 KB Output is correct
12 Correct 116 ms 26116 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 2 ms 2248 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 18 ms 18020 KB Output is correct
9 Correct 17 ms 18268 KB Output is correct
10 Correct 16 ms 17500 KB Output is correct
11 Correct 189 ms 37216 KB Output is correct
12 Correct 191 ms 36948 KB Output is correct
13 Correct 185 ms 37244 KB Output is correct
14 Correct 272 ms 46416 KB Output is correct
15 Correct 318 ms 49492 KB Output is correct
16 Correct 118 ms 26192 KB Output is correct
17 Correct 116 ms 26116 KB Output is correct
18 Correct 496 ms 286292 KB Output is correct
19 Correct 509 ms 297580 KB Output is correct
20 Correct 785 ms 481876 KB Output is correct
21 Correct 437 ms 251984 KB Output is correct
22 Correct 211 ms 28240 KB Output is correct
23 Correct 212 ms 28800 KB Output is correct
24 Correct 461 ms 274260 KB Output is correct