oj.uz

Submission #467189

# Submission time Handle Problem Language Result Execution time Memory
467189 2021-08-22T01:20:02 Z jli12345 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1127 ms 209276 KB 
#include <bits/stdc++.h>
#include "happiness.h"
using namespace std;


typedef long long ll;

struct Node{
    ll sum;
    int lson, rson;

    Node(){
        sum = 0;
        lson = rson = -1;
    }
} st[100100*64];

int nodecnt = 1;

void newnode(int node){
    if (st[node].lson == -1)
        st[node].lson = ++nodecnt;
    if (st[node].rson == -1)
        st[node].rson = ++nodecnt;
}

void U(int node, ll l, ll r, ll ind, ll val){
    if (l > ind || r < ind)
        return;
    if (l == r){
        st[node].sum += val;
        return;
    }
    newnode(node);
    ll mid = (l+r)/2;
    U(st[node].lson, l, mid, ind, val);
    U(st[node].rson, mid+1, r, ind, val);
    st[node].sum = st[st[node].lson].sum+st[st[node].rson].sum;
}

ll Q(int node, ll l, ll r, ll tl, ll tr){
    if (l > tr || r < tl)
        return 0;
    if (l >= tl && r <= tr)
        return st[node].sum;
    ll mid = (l+r)/2;
    newnode(node);
    return Q(st[node].lson, l, mid, tl, tr)+Q(st[node].rson, mid+1, r, tl, tr);
}

bool isValid(){
    ll curval = 2;
    ll sum = 0;
    while (curval <= st[1].sum){
        sum = Q(1, 1, 1e12, 1, curval-1);
        if (curval > sum+1){
            return false;
        }
        curval = sum+2;
       // cout << sum << "\n";
    }
    return true;
}

bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    for (int i = 0; i < coinsCount; i++){
        U(1, 1, 1e12, coins[i], coins[i]);
    }
    return isValid();
}

bool is_happy(int event, int coinsCount, long long coins[]){
    for (int i = 0; i < coinsCount; i++){
        U(1, 1, 1e12, coins[i], event*coins[i]);
    }
    return isValid();
}

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 50 ms 100548 KB Output is correct
2 Correct 49 ms 100456 KB Output is correct
3 Correct 57 ms 100520 KB Output is correct
4 Correct 52 ms 100560 KB Output is correct
5 Correct 50 ms 100456 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100548 KB Output is correct
2 Correct 49 ms 100456 KB Output is correct
3 Correct 57 ms 100520 KB Output is correct
4 Correct 52 ms 100560 KB Output is correct
5 Correct 50 ms 100456 KB Output is correct
6 Correct 52 ms 100524 KB Output is correct
7 Correct 54 ms 100580 KB Output is correct
8 Correct 77 ms 100824 KB Output is correct
9 Correct 78 ms 100792 KB Output is correct
10 Correct 73 ms 100776 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100548 KB Output is correct
2 Correct 49 ms 100456 KB Output is correct
3 Correct 57 ms 100520 KB Output is correct
4 Correct 52 ms 100560 KB Output is correct
5 Correct 50 ms 100456 KB Output is correct
6 Correct 839 ms 104680 KB Output is correct
7 Correct 841 ms 104668 KB Output is correct
8 Correct 950 ms 104672 KB Output is correct
9 Correct 1127 ms 106048 KB Output is correct
10 Correct 1072 ms 106040 KB Output is correct
11 Correct 455 ms 104460 KB Output is correct
12 Correct 468 ms 104616 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 100548 KB Output is correct
2 Correct 49 ms 100456 KB Output is correct
3 Correct 57 ms 100520 KB Output is correct
4 Correct 52 ms 100560 KB Output is correct
5 Correct 50 ms 100456 KB Output is correct
6 Correct 52 ms 100524 KB Output is correct
7 Correct 54 ms 100580 KB Output is correct
8 Correct 77 ms 100824 KB Output is correct
9 Correct 78 ms 100792 KB Output is correct
10 Correct 73 ms 100776 KB Output is correct
11 Correct 839 ms 104680 KB Output is correct
12 Correct 841 ms 104668 KB Output is correct
13 Correct 950 ms 104672 KB Output is correct
14 Correct 1127 ms 106048 KB Output is correct
15 Correct 1072 ms 106040 KB Output is correct
16 Correct 455 ms 104460 KB Output is correct
17 Correct 468 ms 104616 KB Output is correct
18 Runtime error 921 ms 209276 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -