oj.uz

Submission #275981

# Submission time Handle Problem Language Result Execution time Memory
275981 2020-08-20T08:50:49 Z 반딧불(#5115) Happiness (Balkan15_HAPPINESS) C++17
0 / 100
 0 ms 256 KB 
#include <bits/stdc++.h>
#include "happiness.h"

using namespace std;

typedef long long ll;
const ll INF = 1e18;

struct Node{
    ll s, e;
    ll sum = 0;
    ll v = INF, lazy = 0;
    Node *l=nullptr, *r=nullptr;

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

    inline void propagate(){
        if(!lazy) return;
        if(l) l->lazy += lazy;
        if(r) r->lazy += lazy;
        v += lazy;
        lazy = 0;
    }

    inline ll minSum(ll idx){ /// returning sum
        if(idx <= s) return 0;
        if(e < idx) return sum;
        ll ret = 0;
        if(l) ret += l->minSum(idx);
        if(r) ret += r->minSum(idx);
        return ret;
    }

    inline void addKey(ll _s, ll _e, ll val){
        propagate();
        if(e < _s || s > _e) return;
        if(_s <= s && e <= _e){
            lazy += val;
            propagate();
            return;
        }
        if(l) l->addKey(_s, _e, val);
        if(r) r->addKey(_s, _e, val);
        v = min(l?l->v:INF, r?r->v:INF);
    }

    inline void addValue(ll idx, ll val, ll minSumVal){
        propagate();
        if(s==e){
            sum += val;
            if(v == INF) v = minSumVal - idx;
            return;
        }
        ll m = (s+e)/2;
        if(idx <= m){
            if(!l) l = new Node(s, m);
            l->addValue(idx, val, minSumVal);
//            if(!l->sum) delete l, l=nullptr;
        }
        else{
            if(!r) r = new Node(m+1, e);
            r->addValue(idx, val, minSumVal);
//            if(!r->sum) delete r, r=nullptr;
        }
        if(l) l->propagate();
        if(r) r->propagate();
        sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
        v = min(!l ? INF: l->v, !r ? INF : r->v);
    }
};
Node* root;
ll m;

bool isAble(){
    root->propagate();
    if(root->v >= -1) return true;
    return false;
}

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

    for(int i=0; i<coinsCount; i++){
        ll tmp = root->minSum(coins[i]);
        root->addValue(coins[i], coins[i], tmp);
        root->addKey(coins[i]+1, m, coins[i]);
    }
    return isAble();
}

bool is_happy(int event, int coinsCount, ll coins[]){
    for(int i=0; i<coinsCount; i++){
        ll tmp = root->minSum(coins[i]);
        root->addValue(coins[i], coins[i]*event, tmp);
        root->addKey(coins[i]+1, m, 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 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 256 KB Output isn't correct
2 Halted 0 ms 0 KB -