oj.uz

Submission #931842

# Submission time Handle Problem Language Result Execution time Memory
931842 2024-02-22T12:19:41 Z dead0ne Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1095 ms 524288 KB 
#pragma GCC optimize("unroll-loops,Ofast,O3")
#include <bits/stdc++.h>
#include "happiness.h"
#define pb push_back
#define mp make_pair
#define spc << " " <<
#define endl "\n"
#define all(x) x.begin(), x.end()
#define ll long long
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define st first
#define nd second
#define inf 1000000009
#define MOD 1000000007
#define MX 300005
using namespace std;




struct Node{
    ll sum=0, l, r;
    Node *lc = nullptr, *rc = nullptr;
    Node(ll l, ll r) : l(l), r(r) {}
    
    void extend(){
        if(!lc && l<r){
            ll m = (l+r)>>1;
            lc = new Node(l, m);
            rc = new Node(m+1, r);
        }
    }

    void add(ll tar, ll val){
        extend();
        sum += val;
        if(lc){
            if(tar <= lc->r){
                lc->add(tar, val);
            }
            else{
                rc->add(tar,val);
            }
        }
    }

    ll query(ll ql, ll qr){
        if(ql<=l && r<=qr){
            return sum;
        }
        if(l>qr || r<ql){
            return 0;
        }
        extend();
        return lc->query(ql, qr) + rc->query(ql, qr);
    }
};

Node root(0, 0);

bool is_happy(int event, int coinsCount, long long coins[]){
    for(int i=0; i<coinsCount; i++){
        root.add(coins[i], coins[i] * (long long)event);
    }

    ll x = 1;
    while(x <= root.sum){
        ll res = root.query(1, x);
        if(res < x) return false;
        x = res+1;
    }
    return true;
}
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    root.r = maxCoinSize;
    return is_happy(1, coinsCount, coins);
}

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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 3420 KB Output is correct
7 Correct 4 ms 4188 KB Output is correct
8 Correct 31 ms 27212 KB Output is correct
9 Correct 32 ms 27308 KB Output is correct
10 Correct 29 ms 26196 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 347 ms 51024 KB Output is correct
7 Correct 333 ms 54352 KB Output is correct
8 Correct 356 ms 54608 KB Output is correct
9 Correct 492 ms 66900 KB Output is correct
10 Correct 524 ms 71040 KB Output is correct
11 Correct 119 ms 37168 KB Output is correct
12 Correct 119 ms 37296 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 3 ms 3420 KB Output is correct
7 Correct 4 ms 4188 KB Output is correct
8 Correct 31 ms 27212 KB Output is correct
9 Correct 32 ms 27308 KB Output is correct
10 Correct 29 ms 26196 KB Output is correct
11 Correct 347 ms 51024 KB Output is correct
12 Correct 333 ms 54352 KB Output is correct
13 Correct 356 ms 54608 KB Output is correct
14 Correct 492 ms 66900 KB Output is correct
15 Correct 524 ms 71040 KB Output is correct
16 Correct 119 ms 37168 KB Output is correct
17 Correct 119 ms 37296 KB Output is correct
18 Correct 1075 ms 447692 KB Output is correct
19 Correct 1095 ms 457168 KB Output is correct
20 Runtime error 1002 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -