oj.uz

Submission #410386

# Submission time Handle Problem Language Result Execution time Memory
410386 2021-05-22T15:42:21 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
30 / 100
 2000 ms 102528 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) {
            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-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 2 ms 204 KB Output is correct
3 Correct 2 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
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 2 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 13 ms 7884 KB Output is correct
7 Correct 12 ms 8612 KB Output is correct
8 Correct 125 ms 67660 KB Output is correct
9 Correct 112 ms 68292 KB Output is correct
10 Correct 104 ms 66044 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 2 ms 204 KB Output is correct
3 Correct 2 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 1545 ms 91356 KB Output is correct
7 Correct 1512 ms 90656 KB Output is correct
8 Correct 1539 ms 91424 KB Output is correct
9 Execution timed out 2078 ms 102528 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 2 ms 204 KB Output is correct
3 Correct 2 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 13 ms 7884 KB Output is correct
7 Correct 12 ms 8612 KB Output is correct
8 Correct 125 ms 67660 KB Output is correct
9 Correct 112 ms 68292 KB Output is correct
10 Correct 104 ms 66044 KB Output is correct
11 Correct 1545 ms 91356 KB Output is correct
12 Correct 1512 ms 90656 KB Output is correct
13 Correct 1539 ms 91424 KB Output is correct
14 Execution timed out 2078 ms 102528 KB Time limit exceeded
15 Halted 0 ms 0 KB -