oj.uz

Submission #381666

# Submission time Handle Problem Language Result Execution time Memory
381666 2021-03-25T13:55:21 Z ntabc05101 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 594 ms 10092 KB 
#include "happiness.h";
#include<bits/stdc++.h>

#define LL long long

const int log_mx=45;

std::multiset<LL> m[log_mx];
LL sum[log_mx];

void update(LL p, int event) {
        int log_p=0;
        while ((1LL<<(log_p+1)<=p)) log_p++;

        if (event==1) {
                m[log_p].insert(p);
                sum[log_p]+=p;
        }
        else {
                m[log_p].erase(m[log_p].find(p));
                sum[log_p]-=p;
        }
}

bool check() {
        LL current=0;
        for (int i=0; i<log_mx; i++) {
                if (!m[i].empty()) {
                        LL x=*m[i].begin();
                        if (current+1<x) return false;
                        if (m[i].size()>1 and current+x+1<*next(begin(m[i]))) return false;
                        current+=sum[i];
                }
        }

        return true;
}

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

        return check();
}

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

        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:1:23: warning: extra tokens at end of #include directive
    1 | #include "happiness.h";
      |                       ^
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 364 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 9 ms 876 KB Output is correct
9 Correct 9 ms 908 KB Output is correct
10 Correct 7 ms 876 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 236 ms 6008 KB Output is correct
7 Correct 198 ms 5996 KB Output is correct
8 Correct 222 ms 5976 KB Output is correct
9 Correct 594 ms 6056 KB Output is correct
10 Correct 536 ms 8556 KB Output is correct
11 Correct 185 ms 9964 KB Output is correct
12 Correct 198 ms 10092 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 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 9 ms 876 KB Output is correct
9 Correct 9 ms 908 KB Output is correct
10 Correct 7 ms 876 KB Output is correct
11 Correct 236 ms 6008 KB Output is correct
12 Correct 198 ms 5996 KB Output is correct
13 Correct 222 ms 5976 KB Output is correct
14 Correct 594 ms 6056 KB Output is correct
15 Correct 536 ms 8556 KB Output is correct
16 Correct 185 ms 9964 KB Output is correct
17 Correct 198 ms 10092 KB Output is correct
18 Correct 298 ms 5996 KB Output is correct
19 Correct 282 ms 6028 KB Output is correct
20 Correct 476 ms 6628 KB Output is correct
21 Correct 276 ms 6020 KB Output is correct
22 Correct 292 ms 9964 KB Output is correct
23 Correct 219 ms 9964 KB Output is correct
24 Correct 249 ms 6124 KB Output is correct