oj.uz

Submission #931849

# Submission time Handle Problem Language Result Execution time Memory
931849 2024-02-22T12:28:32 Z dead0ne Happiness (Balkan15_HAPPINESS) C++17
60 / 100
 1029 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;

bool is_happy(int event, int coinsCount, long long coins[]){
    for(int i=0; i<coinsCount; i++){
        root->add(coins[i], coins[i] * 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 = new Node(1, 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 3676 KB Output is correct
7 Correct 4 ms 4188 KB Output is correct
8 Correct 29 ms 27228 KB Output is correct
9 Correct 29 ms 27736 KB Output is correct
10 Correct 27 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 318 ms 52816 KB Output is correct
7 Correct 311 ms 52900 KB Output is correct
8 Correct 312 ms 52820 KB Output is correct
9 Correct 459 ms 65088 KB Output is correct
10 Correct 449 ms 69216 KB Output is correct
11 Correct 117 ms 35436 KB Output is correct
12 Correct 117 ms 35408 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 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 4 ms 3676 KB Output is correct
7 Correct 4 ms 4188 KB Output is correct
8 Correct 29 ms 27228 KB Output is correct
9 Correct 29 ms 27736 KB Output is correct
10 Correct 27 ms 26196 KB Output is correct
11 Correct 318 ms 52816 KB Output is correct
12 Correct 311 ms 52900 KB Output is correct
13 Correct 312 ms 52820 KB Output is correct
14 Correct 459 ms 65088 KB Output is correct
15 Correct 449 ms 69216 KB Output is correct
16 Correct 117 ms 35436 KB Output is correct
17 Correct 117 ms 35408 KB Output is correct
18 Correct 998 ms 445056 KB Output is correct
19 Correct 1029 ms 456788 KB Output is correct
20 Runtime error 926 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -