Submission #410368

# Submission time Handle Problem Language Result Execution time Memory
410368 2021-05-22T15:14:16 Z fvogel499 Happiness (Balkan15_HAPPINESS) C++14
Compilation error
0 ms 0 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 int ll
#define ll long long

const int pow2 = 1LL<<40LL;
const int inf = 2e17;

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

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

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

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

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

    int 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;
      |            ^~~~~~~~
/usr/bin/ld: /tmp/ccSf4h6E.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccHFT8SD.o:happiness.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccSf4h6E.o: in function `main':
grader.cpp:(.text.startup+0x96): undefined reference to `init(int, long long, long long*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x160): undefined reference to `is_happy(int, int, long long*)'
collect2: error: ld returned 1 exit status