oj.uz

Submission #467193

# Submission time Handle Problem Language Result Execution time Memory
467193 2021-08-22T02:44:25 Z jli12345 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1891 ms 507924 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[500100*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 243 ms 501512 KB Output is correct
2 Correct 245 ms 501320 KB Output is correct
3 Correct 262 ms 501320 KB Output is correct
4 Correct 242 ms 501288 KB Output is correct
5 Correct 245 ms 501252 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 501512 KB Output is correct
2 Correct 245 ms 501320 KB Output is correct
3 Correct 262 ms 501320 KB Output is correct
4 Correct 242 ms 501288 KB Output is correct
5 Correct 245 ms 501252 KB Output is correct
6 Correct 249 ms 501308 KB Output is correct
7 Correct 247 ms 501260 KB Output is correct
8 Correct 268 ms 501324 KB Output is correct
9 Correct 271 ms 501408 KB Output is correct
10 Correct 267 ms 501396 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 501512 KB Output is correct
2 Correct 245 ms 501320 KB Output is correct
3 Correct 262 ms 501320 KB Output is correct
4 Correct 242 ms 501288 KB Output is correct
5 Correct 245 ms 501252 KB Output is correct
6 Correct 1055 ms 502536 KB Output is correct
7 Correct 1064 ms 502408 KB Output is correct
8 Correct 1120 ms 502392 KB Output is correct
9 Correct 1294 ms 502340 KB Output is correct
10 Correct 1368 ms 502440 KB Output is correct
11 Correct 650 ms 501640 KB Output is correct
12 Correct 655 ms 501488 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 243 ms 501512 KB Output is correct
2 Correct 245 ms 501320 KB Output is correct
3 Correct 262 ms 501320 KB Output is correct
4 Correct 242 ms 501288 KB Output is correct
5 Correct 245 ms 501252 KB Output is correct
6 Correct 249 ms 501308 KB Output is correct
7 Correct 247 ms 501260 KB Output is correct
8 Correct 268 ms 501324 KB Output is correct
9 Correct 271 ms 501408 KB Output is correct
10 Correct 267 ms 501396 KB Output is correct
11 Correct 1055 ms 502536 KB Output is correct
12 Correct 1064 ms 502408 KB Output is correct
13 Correct 1120 ms 502392 KB Output is correct
14 Correct 1294 ms 502340 KB Output is correct
15 Correct 1368 ms 502440 KB Output is correct
16 Correct 650 ms 501640 KB Output is correct
17 Correct 655 ms 501488 KB Output is correct
18 Correct 1504 ms 502520 KB Output is correct
19 Correct 1586 ms 502404 KB Output is correct
20 Correct 1891 ms 503592 KB Output is correct
21 Correct 1205 ms 507332 KB Output is correct
22 Correct 674 ms 507456 KB Output is correct
23 Correct 710 ms 507924 KB Output is correct
24 Correct 1522 ms 507716 KB Output is correct