oj.uz

Submission #789060

# Submission time Handle Problem Language Result Execution time Memory
789060 2023-07-20T23:51:02 Z lamduybao03 Happiness (Balkan15_HAPPINESS) C++14
60 / 100
 1183 ms 524288 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 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);
        }
    }
    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:52:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |             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 304 KB Output is correct
3 Correct 1 ms 312 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 304 KB Output is correct
3 Correct 1 ms 312 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 3220 KB Output is correct
7 Correct 6 ms 3540 KB Output is correct
8 Correct 30 ms 26572 KB Output is correct
9 Correct 33 ms 26836 KB Output is correct
10 Correct 35 ms 25932 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 304 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 364 ms 53392 KB Output is correct
7 Correct 303 ms 52812 KB Output is correct
8 Correct 305 ms 53448 KB Output is correct
9 Correct 518 ms 66520 KB Output is correct
10 Correct 577 ms 70852 KB Output is correct
11 Correct 212 ms 37064 KB Output is correct
12 Correct 206 ms 37200 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 312 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 3220 KB Output is correct
7 Correct 6 ms 3540 KB Output is correct
8 Correct 30 ms 26572 KB Output is correct
9 Correct 33 ms 26836 KB Output is correct
10 Correct 35 ms 25932 KB Output is correct
11 Correct 364 ms 53392 KB Output is correct
12 Correct 303 ms 52812 KB Output is correct
13 Correct 305 ms 53448 KB Output is correct
14 Correct 518 ms 66520 KB Output is correct
15 Correct 577 ms 70852 KB Output is correct
16 Correct 212 ms 37064 KB Output is correct
17 Correct 206 ms 37200 KB Output is correct
18 Correct 1183 ms 425264 KB Output is correct
19 Correct 863 ms 442200 KB Output is correct
20 Runtime error 1022 ms 524288 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -