oj.uz

Submission #275736

# Submission time Handle Problem Language Result Execution time Memory
275736 2020-08-20T07:24:08 Z 반딧불(#5115) Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 3 ms 640 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "happiness.h"

using namespace std;

typedef long long ll;

unordered_set<ll> st;
struct Node{
    ll s, e;
    ll sum = 0;
    Node *l=nullptr, *r=nullptr, *root=nullptr;

    Node(){}
    Node(ll s, ll e, Node *root): s(s), e(e), root(root){}
    ~Node(){
        if(l) delete l;
        if(r) delete r;
    }

    ll minSum(ll idx){ /// returning sum
        if(idx <= s) return 0;
        if(e < idx) return sum;
        ll ret = 0;
        if(l && l->sum) ret += l->minSum(idx);
        if(r && r->sum) ret += r->minSum(idx);
        return ret;
    }
    ll minMax(ll idx){ /// returning value
        if(idx <= s) return 0;
        if(s==e) return s;
        ll m = (s+e)>>1;
        if(idx <= m+1){
            if(l && l->sum) return l->minMax(idx);
            return 0;
        }
        if(r && r->sum){
            ll tmp = r->minMax(idx);
            if(tmp) return tmp;
        }
        if(l && l->sum){
            ll tmp = l->minMax(idx);
            if(tmp) return tmp;
        }
        return 0;
    }
    ll maxMin(ll idx){ /// returning value
        if(e <= idx) return LLONG_MAX;
        if(s==e) return s;
        ll m = (s+e)>>1;
        if(m <= idx){
            if(r && r->sum) return r->maxMin(idx);
            return LLONG_MAX;
        }
        if(l && l->sum){
            ll tmp = l->maxMin(idx);
            if(tmp != LLONG_MAX) return tmp;
        }
        if(r && r->sum){
            ll tmp = r->maxMin(idx);
            if(tmp != LLONG_MAX) return tmp;
        }
        return LLONG_MAX;
    }

    void addValue(ll idx, ll val){
        if(s==e){
            sum += val;

            ll lv = root->minMax(idx);
            ll rv = root->maxMin(idx);

            if(sum){ /// adding
                if(lv*2 < idx) st.insert(idx);
                else st.erase(idx);
                if(rv != LLONG_MAX){
                    if(idx*2 < rv) st.insert(rv);
                    else st.erase(rv);
                }
            }
            else{ /// deleted
                st.erase(idx);
                if(rv != LLONG_MAX){
                    if(lv*2 < rv) st.insert(rv);
                    else st.erase(rv);
                }
            }

            return;
        }
        ll m = (s+e)>>1;
        if(idx <= m){
            if(!l) l = new Node(s, m, root);
            l->addValue(idx, val);
            if(!l->sum) delete l;
        }
        else{
            if(!r) r = new Node(m+1, e, root);
            r->addValue(idx, val);
            if(!r->sum) delete r;
        }
        sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
    }
};
Node* root;

int n, cnt;

bool isAble(){
    for(auto &x: st){
//        printf("strange(%lld) ", x);
        if(root->minSum(x) + 1 < x) return false;
    }
    return true;
}

bool init(int coinsCount, ll maxCoinSize, ll coins[]) {
    n = coinsCount;
    root = new Node();
    root->s= 1, root->e = maxCoinSize;
    root->root = root;

    for(int i=0; i<n; i++){
        root->addValue(coins[i], coins[i]);
    }
    return isAble();
}

bool is_happy(int event, int coinsCount, ll coins[]) {
    n += coinsCount * event;
    for(int i=0; i<coinsCount; i++) root->addValue(coins[i], coins[i] * event);
    return isAble();
}

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

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -