oj.uz

Submission #789062

# Submission time Handle Problem Language Result Execution time Memory
789062 2023-07-21T00:14:32 Z lamduybao03 Happiness (Balkan15_HAPPINESS) C++14
100 / 100
 1424 ms 248792 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

struct Type {
    int sum;
    int max_d;
    Type() {
        sum = 0;
        max_d = 0;
    }
    void update(int id, int k) {
        if(id == 1) {
            max_d = k;
            sum += k;
        }
        else {
            sum -= k;
            if(sum == 0) {
                max_d = 0;
            }
        }
    }
};
struct Node {
    Node* left;
    Node* right;
    Type d;
    Type merge(Type a, Type b) {
        Type c;
        c.sum = a.sum + b.sum;
        c.max_d = max(a.max_d, b.max_d - a.sum);
        return c;
    }
    Node() {
        left = right = nullptr;
    }
    Node* new_node(Node* p) {
        if(p == nullptr)
            return new Node();
        else
            return p;
    }
    void erase_child() {
        if(d.sum == 0) {
            delete left;
            delete right;
            left = right = nullptr;
        }
    }
    void add_child() {
        left = new_node(left);
        right = new_node(right);
    }
    void update(int i, int x, int l, int r) {
        if(l == i && i == r)
            d.update(x, i);
        else if(l <= i && i <= r) {
            int m = l + r >> 1;
            add_child();
            left->update(i, x, l, m);
            right->update(i, x, m+1, r);
            d = merge(left->d, right->d);
            erase_child();
        }
    }
    int query() {
        return d.max_d <= 1;
    }
    void update(int i, int x) {
        update(i, x, 0, 1LL << 40);
    }
} root;

bool init(int32_t n, int m, int* a) {
    for(int i = 0; i < n; i++) {
        root.update(a[i], 1);
    }
    return root.query();
}
bool is_happy(int32_t id, int32_t n, int* a) {
    for(int i = 0; i < n; i++) {
        root.update(a[i], id);
    }
    return root.query();
}

Compilation message

happiness.cpp: In member function 'void Node::update(long long int, long long int, long long int, long long int)':
happiness.cpp:59:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   59 |             int m = l + r >> 1;
      |                     ~~^~~
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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 3136 KB Output is correct
7 Correct 4 ms 3156 KB Output is correct
8 Correct 32 ms 25684 KB Output is correct
9 Correct 32 ms 25640 KB Output is correct
10 Correct 30 ms 25568 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 391 ms 37472 KB Output is correct
7 Correct 381 ms 37572 KB Output is correct
8 Correct 369 ms 37364 KB Output is correct
9 Correct 627 ms 38764 KB Output is correct
10 Correct 612 ms 48652 KB Output is correct
11 Correct 236 ms 36996 KB Output is correct
12 Correct 245 ms 37148 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 3136 KB Output is correct
7 Correct 4 ms 3156 KB Output is correct
8 Correct 32 ms 25684 KB Output is correct
9 Correct 32 ms 25640 KB Output is correct
10 Correct 30 ms 25568 KB Output is correct
11 Correct 391 ms 37472 KB Output is correct
12 Correct 381 ms 37572 KB Output is correct
13 Correct 369 ms 37364 KB Output is correct
14 Correct 627 ms 38764 KB Output is correct
15 Correct 612 ms 48652 KB Output is correct
16 Correct 236 ms 36996 KB Output is correct
17 Correct 245 ms 37148 KB Output is correct
18 Correct 952 ms 223792 KB Output is correct
19 Correct 933 ms 222936 KB Output is correct
20 Correct 1424 ms 248792 KB Output is correct
21 Correct 813 ms 225612 KB Output is correct
22 Correct 273 ms 39168 KB Output is correct
23 Correct 262 ms 39580 KB Output is correct
24 Correct 916 ms 226096 KB Output is correct