oj.uz

Submission #381658

# Submission time Handle Problem Language Result Execution time Memory
381658 2021-03-25T13:14:54 Z ntabc05101 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1520 ms 380388 KB 
#include "happiness.h"
#include<bits/stdc++.h>

#define LL long long

struct Node {
        LL l, r, value;
        Node *lc, *rc;

        Node(LL L, LL R): l(L), r(R), value(0), lc(nullptr), rc(nullptr) {};

        void update(LL p, LL delta) {
                value+=delta;
                if (l!=r) {
                        LL mid=l+r>>1;
                        if (p>mid) {
                                if (!rc) rc=new Node(mid+1, r);
                                rc->update(p, delta);
                        }
                        else {
                                if (!lc) lc=new Node(l, mid);
                                lc->update(p, delta);
                        }
                }
        }

        LL get(LL left, LL right) {
                if (left>r or right<l) return 0;
                if (left<=l and right>=r) return value;

                LL ret=0;
                if (lc) ret+=lc->get(left, right);
                if (rc) ret+=rc->get(left, right);
                return ret;
        }
};

Node* root;

bool check() {
        LL current=0, sum=root->value;
        while (current<sum) {
                LL t=root->get(1, current);
                if (t<current) return false;
                current=t+1;
        }

        return true;
}

bool init(int coinsCount, LL maxCoinSize, LL coins[]) {
        root=new Node(1, maxCoinSize);
        for (int i=0; i<coinsCount; i++) {
                root->update(coins[i], coins[i]);
        }

        return check();
}

bool is_happy(int event, int coinsCount, LL coins[]) {
        for (int i=0; i<coinsCount; i++) {
                root->update(coins[i], event*coins[i]);
        }

        return check();
}

/*int main() {
        std::ios_base::sync_with_stdio(0); std::cin.tie(0);

        int n; LL m; std::cin>>n>>m;
        LL coins[n];
        for (int i=0; i<n; i++) std::cin>>coins[i];
        std::cout<<init(n, m, coins)<<"\n";

        int q; std::cin>>q;
        while (q--) {
                int e, k; std::cin>>e>>k;
                LL coins[k]; 
                for (int i=0; i<k; i++) std::cin>>coins[i];
                std::cout<<is_happy(e, k, coins)<<"\n";
        }

        return 0;
}*/

Compilation message

happiness.cpp: In member function 'void Node::update(long long int, long long int)':
happiness.cpp:15:33: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |                         LL mid=l+r>>1;
      |                                ~^~
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 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 1900 KB Output is correct
7 Correct 4 ms 2028 KB Output is correct
8 Correct 29 ms 14188 KB Output is correct
9 Correct 30 ms 14316 KB Output is correct
10 Correct 27 ms 13804 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 468 ms 37596 KB Output is correct
7 Correct 480 ms 37228 KB Output is correct
8 Correct 544 ms 37608 KB Output is correct
9 Correct 671 ms 48808 KB Output is correct
10 Correct 653 ms 52844 KB Output is correct
11 Correct 173 ms 37108 KB Output is correct
12 Correct 180 ms 37228 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 1900 KB Output is correct
7 Correct 4 ms 2028 KB Output is correct
8 Correct 29 ms 14188 KB Output is correct
9 Correct 30 ms 14316 KB Output is correct
10 Correct 27 ms 13804 KB Output is correct
11 Correct 468 ms 37596 KB Output is correct
12 Correct 480 ms 37228 KB Output is correct
13 Correct 544 ms 37608 KB Output is correct
14 Correct 671 ms 48808 KB Output is correct
15 Correct 653 ms 52844 KB Output is correct
16 Correct 173 ms 37108 KB Output is correct
17 Correct 180 ms 37228 KB Output is correct
18 Correct 1067 ms 226156 KB Output is correct
19 Correct 1095 ms 234988 KB Output is correct
20 Correct 1520 ms 380388 KB Output is correct
21 Correct 815 ms 199428 KB Output is correct
22 Correct 225 ms 39388 KB Output is correct
23 Correct 228 ms 39660 KB Output is correct
24 Correct 1032 ms 216812 KB Output is correct