oj.uz

Submission #275992

# Submission time Handle Problem Language Result Execution time Memory
275992 2020-08-20T08:57:45 Z 반딧불(#5115) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 210048 KB 
#include <bits/stdc++.h>
#include "happiness.h"

using namespace std;

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

int nodeCount;

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

    Node(){}
    Node(ll s, ll e): s(s), e(e){
        m = (s+e)>>1;
        nodeCount++;
    }
    ~Node(){
        nodeCount--;
        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;
        }
        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;

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

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

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

bool is_happy(int event, int coinsCount, ll coins[]){
    for(int i=0; i<coinsCount; i++){
        root->addValue(coins[i], coins[i]*event, root->minSum(coins[i]));
        root->addKey(coins[i]+1, m, coins[i]*event);
    }
    assert(nodeCount <= 8000000);
    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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 56 ms 22136 KB Output is correct
9 Correct 54 ms 22124 KB Output is correct
10 Correct 48 ms 22048 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 903 ms 36504 KB Output is correct
7 Correct 865 ms 36344 KB Output is correct
8 Correct 893 ms 36600 KB Output is correct
9 Correct 1381 ms 36644 KB Output is correct
10 Correct 1415 ms 48708 KB Output is correct
11 Correct 453 ms 43512 KB Output is correct
12 Correct 471 ms 43768 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 2816 KB Output is correct
7 Correct 5 ms 2816 KB Output is correct
8 Correct 56 ms 22136 KB Output is correct
9 Correct 54 ms 22124 KB Output is correct
10 Correct 48 ms 22048 KB Output is correct
11 Correct 903 ms 36504 KB Output is correct
12 Correct 865 ms 36344 KB Output is correct
13 Correct 893 ms 36600 KB Output is correct
14 Correct 1381 ms 36644 KB Output is correct
15 Correct 1415 ms 48708 KB Output is correct
16 Correct 453 ms 43512 KB Output is correct
17 Correct 471 ms 43768 KB Output is correct
18 Correct 1601 ms 192448 KB Output is correct
19 Correct 1637 ms 192300 KB Output is correct
20 Execution timed out 2097 ms 210048 KB Time limit exceeded
21 Halted 0 ms 0 KB -