Submission #410373

#	Time	Username	Problem	Language	Result	Execution time	Memory
410373		fvogel499	Happiness (Balkan15_HAPPINESS)	C++14	40 / 100	1976 ms	122388 KiB

happiness

/*
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 <happiness.h>

using namespace std;

#define ll ll
#define ll long long

const ll pow2 = 1LL<<20LL; // or 40
const ll inf = 2e17;

struct Node {
    Node(ll llb, ll 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(ll l, ll r, ll 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);
        }
    }
    ll lb, rb, mxv, lzy;
    Node* ln, *rn;
};

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

bool check() {
    if (s.size() == 0) return true;
    else {
        ll 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(ll n, ll* b) {
    for (ll 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(ll n, ll* b) {
    for (ll 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, ll maxVal, ll* 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, ll* b) {
    if (event == 1) add(n, b);
    else rem(n, b);
    return check();
}

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

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

//     ll d = 0;
//     d++;
// }

Compilation message (stderr)

happiness.cpp:23: warning: "ll" redefined
   23 | #define ll long long
      | 
happiness.cpp:22: note: this is the location of the previous definition
   22 | #define ll ll
      | 
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