oj.uz

Submission #1019736

# Submission time Handle Problem Language Result Execution time Memory
1019736 2024-07-11T08:23:57 Z NoLove Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 2000 ms 524288 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 = 1e7 + 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);
    }
    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

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.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 17 ms 17952 KB Output is correct
9 Correct 17 ms 18268 KB Output is correct
10 Correct 15 ms 17496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 159 ms 34180 KB Output is correct
7 Correct 185 ms 33868 KB Output is correct
8 Correct 169 ms 34128 KB Output is correct
9 Correct 237 ms 42028 KB Output is correct
10 Correct 286 ms 44880 KB Output is correct
11 Correct 110 ms 22352 KB Output is correct
12 Correct 109 ms 22352 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 2392 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 17 ms 17952 KB Output is correct
9 Correct 17 ms 18268 KB Output is correct
10 Correct 15 ms 17496 KB Output is correct
11 Correct 159 ms 34180 KB Output is correct
12 Correct 185 ms 33868 KB Output is correct
13 Correct 169 ms 34128 KB Output is correct
14 Correct 237 ms 42028 KB Output is correct
15 Correct 286 ms 44880 KB Output is correct
16 Correct 110 ms 22352 KB Output is correct
17 Correct 109 ms 22352 KB Output is correct
18 Correct 466 ms 286292 KB Output is correct
19 Correct 463 ms 297668 KB Output is correct
20 Execution timed out 2799 ms 524288 KB Time limit exceeded
21 Halted 0 ms 0 KB -