oj.uz

Submission #410371

# Submission time Handle Problem Language Result Execution time Memory
410371 2021-05-22T15:16:18 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 108292 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<<40LL;
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 300 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 15 ms 7860 KB Output is correct
7 Correct 12 ms 8632 KB Output is correct
8 Correct 111 ms 67836 KB Output is correct
9 Correct 107 ms 68644 KB Output is correct
10 Correct 100 ms 66260 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 1562 ms 94364 KB Output is correct
7 Correct 1490 ms 93768 KB Output is correct
8 Correct 1496 ms 94524 KB Output is correct
9 Execution timed out 2077 ms 108292 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 2 ms 332 KB Output is correct
6 Correct 15 ms 7860 KB Output is correct
7 Correct 12 ms 8632 KB Output is correct
8 Correct 111 ms 67836 KB Output is correct
9 Correct 107 ms 68644 KB Output is correct
10 Correct 100 ms 66260 KB Output is correct
11 Correct 1562 ms 94364 KB Output is correct
12 Correct 1490 ms 93768 KB Output is correct
13 Correct 1496 ms 94524 KB Output is correct
14 Execution timed out 2077 ms 108292 KB Time limit exceeded
15 Halted 0 ms 0 KB -