oj.uz

Submission #1043275

# Submission time Handle Problem Language Result Execution time Memory
1043275 2024-08-04T07:21:18 Z BF001 Happiness (Balkan15_HAPPINESS) C++17
100 / 100
 807 ms 380244 KB 
#include "happiness.h"
#include<bits/stdc++.h>
using namespace std;


struct node{
    long long l, r, val;
    node* lc,  *rc;
    
    node(long long l1, long long r1){
        l = l1, r = r1;
        val = 0;
        lc = NULL;
        rc = NULL;
    }

    void ud(long long pos, long long v){
        val += v;
        if (l == r) return;
        long long mid = (l + r) >> 1;
        if (pos > mid){
            if (!rc) rc = new node(mid + 1, r);
            rc -> ud(pos, v);
        }
        else{
            if (!lc) lc = new node(l, mid);
            lc -> ud(pos, v);
        }
    }

    long long get(long long u, long long v){
        if (l > v || r < u) return 0;
        if (l >= u && r <= v) return val;
        long long t = 0, tt = 0;
        if (lc) t = lc -> get(u, v);
        if (rc) tt = rc -> get(u, v);
        return (t + tt);
    }

};

node *root;

bool check(){
    long long mx = root -> val;
    long long cur = 1;
    while (cur < mx){
        long long t = root -> get(1, cur);
        if (t < cur) return false;
        cur = t + 1;
    }
    return true;
}
 
bool init(int coinsCount, long long maxCoinSize, long long coins[]){
    root = new node(1, maxCoinSize);
    for (int i = 0; i < coinsCount; i++){
        root -> ud(coins[i], coins[i]);
    }
    return check();
}

bool is_happy(int event, int coinsCount, long long coins[]){
    for (int i = 0; i < coinsCount; i++)
		root->ud(coins[i], event * coins[i]);
	return check();
}

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 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 0 ms 348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 2 ms 1992 KB Output is correct
7 Correct 2 ms 2140 KB Output is correct
8 Correct 14 ms 14028 KB Output is correct
9 Correct 19 ms 14172 KB Output is correct
10 Correct 17 ms 13660 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 207 ms 37460 KB Output is correct
7 Correct 253 ms 36956 KB Output is correct
8 Correct 253 ms 37460 KB Output is correct
9 Correct 323 ms 48724 KB Output is correct
10 Correct 320 ms 52816 KB Output is correct
11 Correct 93 ms 37176 KB Output is correct
12 Correct 93 ms 37100 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 ms 348 KB Output is correct
6 Correct 2 ms 1992 KB Output is correct
7 Correct 2 ms 2140 KB Output is correct
8 Correct 14 ms 14028 KB Output is correct
9 Correct 19 ms 14172 KB Output is correct
10 Correct 17 ms 13660 KB Output is correct
11 Correct 207 ms 37460 KB Output is correct
12 Correct 253 ms 36956 KB Output is correct
13 Correct 253 ms 37460 KB Output is correct
14 Correct 323 ms 48724 KB Output is correct
15 Correct 320 ms 52816 KB Output is correct
16 Correct 93 ms 37176 KB Output is correct
17 Correct 93 ms 37100 KB Output is correct
18 Correct 535 ms 225872 KB Output is correct
19 Correct 543 ms 234732 KB Output is correct
20 Correct 807 ms 380244 KB Output is correct
21 Correct 434 ms 199252 KB Output is correct
22 Correct 130 ms 39252 KB Output is correct
23 Correct 126 ms 39600 KB Output is correct
24 Correct 507 ms 216660 KB Output is correct