oj.uz

Submission #931841

# Submission time Handle Problem Language Result Execution time Memory
931841 2024-02-22T12:13:38 Z dead0ne Happiness (Balkan15_HAPPINESS) C++17
10 / 100
 334 ms 54212 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(int ql, int 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 1 ms 600 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Incorrect 3 ms 3416 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Incorrect 334 ms 54212 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 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 0 ms 348 KB Output is correct
6 Incorrect 3 ms 3416 KB Output isn't correct
7 Halted 0 ms 0 KB -