Submission #410363

# Submission time Handle Problem Language Result Execution time Memory
410363 2021-05-22T15:12:07 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
Compilation error
0 ms 0 KB
/*
File created on 05/22/2021 at 14:27:37.
Link to problem: https://oj.uz/problem/view/Balkan15_HAPPINESS
*/

#include <iostream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <cstring>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>

#include <hapiness.h>

using namespace std;

#define int ll
#define ll long long

const int pow2 = 1LL<<40LL;
const int inf = 2e17;

struct Node {
    Node(int llb, int lrb) {
        lb = llb;
        rb = lrb;
        mxv = 0;
        lzy = 0;
        ln = nullptr;
        rn = nullptr;
    }
    void extend() {
        if (ln == nullptr and rn == nullptr) {
            ln = new Node(lb, (lb+rb)/2);
            ln->mxv = mxv-(rb-lb+1)/2;
            rn = new Node((lb+rb)/2+1, rb);
            rn->mxv = mxv;
        }
    }
    void propag() {
        if (lb != rb) {
            extend();
            ln->lzy += lzy;
            rn->lzy += lzy;
        }
        mxv += lzy;
        lzy = 0;
    }
    void rangeUpdate(int l, int r, int v) {
        if (lb > r or l > rb) propag();
        else if (l <= lb and rb <= r) {
            lzy += v;
            propag();
        }
        else {
            propag();
            ln->rangeUpdate(l, r, v);
            rn->rangeUpdate(l, r, v);
            mxv = max(ln->mxv, rn->mxv);
        }
    }
    int lb, rb, mxv, lzy;
    Node* ln, *rn;
};

Node* root;
map<int, int> s;

bool check() {
    if (s.size() == 0) return true;
    else {
        int mxv = (*prev(s.end())).first;
        root->rangeUpdate(mxv+1, pow2-1, -inf);
        bool ans = (root->mxv <= 1);
        root->rangeUpdate(mxv+1, pow2-1, +inf);
        return ans;
    }
}

void add(int n, int b []) {
    for (int i = 0; i < n; i++) {
        root->rangeUpdate(b[i]+1, pow2-1, -b[i]);
        if (s.find(b[i]) == s.end() or s[b[i]] == 0) {
            s[b[i]] = 1;
            root->rangeUpdate(b[i], b[i], +inf);
        }
        else s[b[i]]++;
    }
}

void rem(int n, int b []) {
    for (int i = 0; i < n; i++) {
        root->rangeUpdate(b[i]+1, pow2-1, +b[i]);
        s[b[i]]--;
        if (s[b[i]] == 0) {
            s.erase(b[i]);
            root->rangeUpdate(b[i], b[i], -inf);
        }
    }
}

bool init(int n, int maxVal, int b []) {
    root = new Node(0, pow2-1);
    root->rangeUpdate(0, pow2-1, pow2-1);
    root->rangeUpdate(0, pow2-1, -inf);
    add(n, b);
    return check();
}

bool is_happy(int event, int n, int b []) {
    if (event == 1) add(n, b);
    else rem(n, b);
    return check();
}

// signed main() {
//     cin.tie(0);
//     // ios_base::sync_with_stdio(0);

//     int n, maxVal;
//     cin >> n >> maxVal;
//     int b [n];
//     for (int i = 0; i < n; i++) cin >> b[i];
//     cout << init(n, maxVal, b) << endl;
//     int nbReq;
//     cin >> nbReq;
//     for (int _ = 0; _ < nbReq; _++) {
//         int event, ln;
//         cin >> event >> ln;
//         int lb [ln];
//         for (int i = 0; i < ln; i++) cin >> lb[i];
//         cout << is_happy(event, ln, lb) << endl;
//     }

//     int d = 0;
//     d++;
// }

Compilation message

happiness.cpp:18:10: fatal error: hapiness.h: No such file or directory
   18 | #include <hapiness.h>
      |          ^~~~~~~~~~~~
compilation terminated.
grader.cpp: In function 'int main()':
grader.cpp:16:12: warning: unused variable 'max_code' [-Wunused-variable]
   16 |  long long max_code;
      |            ^~~~~~~~