oj.uz

Submission #802158

# Submission time Handle Problem Language Result Execution time Memory
802158 2023-08-02T10:32:03 Z atom Happiness (Balkan15_HAPPINESS) C++17
40 / 100
 437 ms 524288 KB 
#include "bits/stdc++.h"
#include "happiness.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define REP(i, b) for(int i = 0; i < b; i++)
#define PER(i, b) for(int i = b - 1; i >= 0; i--)
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#ifdef JASPER2
#include "debug.h"
#else
#define debug(...) 166
#endif

using pii = pair < int, int >;
const ll LINF = 1e12 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int MAX = 2e5 + 5;

struct DynamicSegmentTree {
    struct Node {
        ll lx, rx, val;
        Node *l, *r;
        Node(ll _lx, ll _rx) {
            lx = _lx;
            rx = _rx;
            l = r = NULL;
        }
    };
    Node *p;
    void rmk(ll l, ll r) {
        p = new Node(1, LINF);
    }

    void upd(Node *root, ll pos, ll val) {
        root->val += val;
        if (root->lx != root->rx) {
            int m = (root->lx + root->rx) >> 1;
            if (pos <= m) {
                if (root->l == NULL)
                    root->l = new Node(root->lx, m);
                upd(root->l, pos, val);
            }
            else {
                if (root->r == NULL)
                    root->r = new Node(m + 1, root->rx);
                upd(root->r, pos, val);
            }
        }
    }

    ll qry(Node *root, ll l, ll r) {
        if (root->lx > r || root->rx < l)
            return 0;
        if (l <= root->lx && root->rx <= r)
            return root->val;
        ll ans = 0;
        if (root->l != NULL)
            ans += qry(root->l, l, r);
        if (root->r != NULL)
            ans += qry(root->r, l, r);
        return ans;
    }

    ll check() {
        ll ai = 1, lim = p->val;
        while (ai < lim) {
            ll sum = qry(p, 1, ai);
            if (sum < ai)
                return 0;
            ai = sum + 1;
        }
        return 1;
    }
};
ll n, m, q;
ll a[MAX];
DynamicSegmentTree st;

bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
    st.rmk(1, maxCoinSize);
    sort(coins, coins + coinsCount);

    for (int i = 0; i < coinsCount; ++i)
        st.upd(st.p, coins[i], coins[i]);
    return st.check();
}

bool is_happy(int event, int coinsCount, ll coins[]) {
    for (int i = 0; i < coinsCount; ++i)
        st.upd(st.p, coins[i], 1ll * event * coins[i]);
    return st.check();
}

//void run_case() {
//    cin >> n >> m;
//    for (int i = 1; i <= n; ++i)
//        cin >> a[i];
//
//    DynamicSegmentTree st(1, m);
//    for (int i = 1; i <= n; ++i)
//        st.upd(st.p, a[i], a[i]);
//    cout << st.check() << "\n";
//
//    cin >> q;
//    while (q--) {
//        int cmd, k;
//        cin >> cmd >> k;
//        array <ll, 12> c;
//        for (int i = 0; i < k; ++i)
//            cin >> c[i];
//        for (int i = 0; i < k; ++i)
//            st.upd(st.p, c[i], c[i] * cmd);
//        cout << st.check() << "\n";
//    }
//}

//signed main() {
//    cin.tie(0) -> sync_with_stdio(0);
//    #ifdef JASPER2
//        freopen("in1", "r", stdin);
//    #endif
//
//    int Test = 1;
//    //cin >> Test;
//    for (int test = 1; test <= Test; test++){
//
//        run_case();
//    }
//}

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 1 ms 212 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 374 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 271 ms 37648 KB Output is correct
7 Correct 280 ms 37232 KB Output is correct
8 Correct 329 ms 37744 KB Output is correct
9 Correct 410 ms 48964 KB Output is correct
10 Correct 437 ms 53120 KB Output is correct
11 Correct 128 ms 37040 KB Output is correct
12 Correct 122 ms 37208 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Runtime error 374 ms 524288 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -