oj.uz

Submission #410374

# Submission time Handle Problem Language Result Execution time Memory
410374 2021-05-22T15:32:07 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 102320 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 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

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 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 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 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 7832 KB Output is correct
7 Correct 12 ms 8640 KB Output is correct
8 Correct 112 ms 67668 KB Output is correct
9 Correct 115 ms 68292 KB Output is correct
10 Correct 115 ms 66068 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 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1519 ms 91204 KB Output is correct
7 Correct 1512 ms 90432 KB Output is correct
8 Correct 1537 ms 91172 KB Output is correct
9 Execution timed out 2089 ms 102320 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 204 KB Output is correct
3 Correct 2 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 11 ms 7832 KB Output is correct
7 Correct 12 ms 8640 KB Output is correct
8 Correct 112 ms 67668 KB Output is correct
9 Correct 115 ms 68292 KB Output is correct
10 Correct 115 ms 66068 KB Output is correct
11 Correct 1519 ms 91204 KB Output is correct
12 Correct 1512 ms 90432 KB Output is correct
13 Correct 1537 ms 91172 KB Output is correct
14 Execution timed out 2089 ms 102320 KB Time limit exceeded
15 Halted 0 ms 0 KB -