oj.uz

Submission #275988

# Submission time Handle Problem Language Result Execution time Memory
275988 2020-08-20T08:54:14 Z 반딧불(#5115) Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 2000 ms 168388 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;
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;

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);
    }
    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 6 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Correct 51 ms 17784 KB Output is correct
9 Correct 57 ms 17784 KB Output is correct
10 Correct 48 ms 17784 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 821 ms 29432 KB Output is correct
7 Correct 775 ms 29304 KB Output is correct
8 Correct 787 ms 29304 KB Output is correct
9 Correct 1380 ms 29340 KB Output is correct
10 Correct 1497 ms 39116 KB Output is correct
11 Correct 443 ms 34880 KB Output is correct
12 Correct 454 ms 34936 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 6 ms 2304 KB Output is correct
7 Correct 5 ms 2304 KB Output is correct
8 Correct 51 ms 17784 KB Output is correct
9 Correct 57 ms 17784 KB Output is correct
10 Correct 48 ms 17784 KB Output is correct
11 Correct 821 ms 29432 KB Output is correct
12 Correct 775 ms 29304 KB Output is correct
13 Correct 787 ms 29304 KB Output is correct
14 Correct 1380 ms 29340 KB Output is correct
15 Correct 1497 ms 39116 KB Output is correct
16 Correct 443 ms 34880 KB Output is correct
17 Correct 454 ms 34936 KB Output is correct
18 Correct 1565 ms 154232 KB Output is correct
19 Correct 1638 ms 154220 KB Output is correct
20 Execution timed out 2094 ms 168388 KB Time limit exceeded
21 Halted 0 ms 0 KB -