oj.uz

Submission #275986

# Submission time Handle Problem Language Result Execution time Memory
275986 2020-08-20T08:53:07 Z 반딧불(#5115) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 168152 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(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);
    }
    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 1 ms 256 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 1 ms 256 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 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Correct 53 ms 17740 KB Output is correct
9 Correct 52 ms 17784 KB Output is correct
10 Correct 48 ms 17816 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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 909 ms 29480 KB Output is correct
7 Correct 821 ms 29432 KB Output is correct
8 Correct 946 ms 29612 KB Output is correct
9 Correct 1363 ms 29560 KB Output is correct
10 Correct 1388 ms 39160 KB Output is correct
11 Correct 449 ms 34896 KB Output is correct
12 Correct 463 ms 34988 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 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 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Correct 53 ms 17740 KB Output is correct
9 Correct 52 ms 17784 KB Output is correct
10 Correct 48 ms 17816 KB Output is correct
11 Correct 909 ms 29480 KB Output is correct
12 Correct 821 ms 29432 KB Output is correct
13 Correct 946 ms 29612 KB Output is correct
14 Correct 1363 ms 29560 KB Output is correct
15 Correct 1388 ms 39160 KB Output is correct
16 Correct 449 ms 34896 KB Output is correct
17 Correct 463 ms 34988 KB Output is correct
18 Correct 1535 ms 154232 KB Output is correct
19 Correct 1560 ms 154192 KB Output is correct
20 Execution timed out 2091 ms 168152 KB Time limit exceeded
21 Halted 0 ms 0 KB -