oj.uz

Submission #410373

# Submission time Handle Problem Language Result Execution time Memory
410373 2021-05-22T15:30:09 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
40 / 100
 1976 ms 122388 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 <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

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

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Correct 1134 ms 91376 KB Output is correct
7 Correct 1106 ms 90436 KB Output is correct
8 Correct 1139 ms 91452 KB Output is correct
9 Correct 1858 ms 107732 KB Output is correct
10 Correct 1976 ms 122388 KB Output is correct
11 Correct 721 ms 60472 KB Output is correct
12 Correct 753 ms 60784 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 204 KB Output is correct
6 Incorrect 1 ms 332 KB Output isn't correct
7 Halted 0 ms 0 KB -