oj.uz

Submission #467191

# Submission time Handle Problem Language Result Execution time Memory
467191 2021-08-22T02:40:13 Z jli12345 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1660 ms 408644 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[200100*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 <= min((ll)1e12, 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 97 ms 200756 KB Output is correct
2 Correct 102 ms 200732 KB Output is correct
3 Correct 107 ms 200656 KB Output is correct
4 Correct 110 ms 200752 KB Output is correct
5 Correct 100 ms 200680 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 200756 KB Output is correct
2 Correct 102 ms 200732 KB Output is correct
3 Correct 107 ms 200656 KB Output is correct
4 Correct 110 ms 200752 KB Output is correct
5 Correct 100 ms 200680 KB Output is correct
6 Correct 100 ms 200680 KB Output is correct
7 Correct 100 ms 200680 KB Output is correct
8 Correct 123 ms 200796 KB Output is correct
9 Correct 123 ms 200844 KB Output is correct
10 Correct 131 ms 200820 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 200756 KB Output is correct
2 Correct 102 ms 200732 KB Output is correct
3 Correct 107 ms 200656 KB Output is correct
4 Correct 110 ms 200752 KB Output is correct
5 Correct 100 ms 200680 KB Output is correct
6 Correct 927 ms 201796 KB Output is correct
7 Correct 892 ms 201764 KB Output is correct
8 Correct 1004 ms 201760 KB Output is correct
9 Correct 1176 ms 202012 KB Output is correct
10 Correct 1164 ms 201812 KB Output is correct
11 Correct 517 ms 200968 KB Output is correct
12 Correct 503 ms 201156 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 200756 KB Output is correct
2 Correct 102 ms 200732 KB Output is correct
3 Correct 107 ms 200656 KB Output is correct
4 Correct 110 ms 200752 KB Output is correct
5 Correct 100 ms 200680 KB Output is correct
6 Correct 100 ms 200680 KB Output is correct
7 Correct 100 ms 200680 KB Output is correct
8 Correct 123 ms 200796 KB Output is correct
9 Correct 123 ms 200844 KB Output is correct
10 Correct 131 ms 200820 KB Output is correct
11 Correct 927 ms 201796 KB Output is correct
12 Correct 892 ms 201764 KB Output is correct
13 Correct 1004 ms 201760 KB Output is correct
14 Correct 1176 ms 202012 KB Output is correct
15 Correct 1164 ms 201812 KB Output is correct
16 Correct 517 ms 200968 KB Output is correct
17 Correct 503 ms 201156 KB Output is correct
18 Correct 1434 ms 201940 KB Output is correct
19 Correct 1411 ms 201824 KB Output is correct
20 Runtime error 1660 ms 408644 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -