oj.uz

Submission #526657

# Submission time Handle Problem Language Result Execution time Memory
526657 2022-02-15T21:21:22 Z LFFB Growing Trees (BOI11_grow) C++14
40 / 100
 1000 ms 11312 KB 
#include <iostream>
#include <vector>
#include <algorithm>

#define debug(args...) //printf(args)
#define pair(x, y) std::make_pair(x, y)

const int MAX_N = 100000 + 10;
const int MAX_NODES = 4 * MAX_N;

struct Node {
    bool leaf;
    int height;
    int first;
    int last;
    int lazySum;

    Node() {
        height = 0;
        first = 0;
        last = 0;
        lazySum = 0;
        leaf = true;
    }
    Node(int h) {
        height = h;
        first = height;
        last = height;
        lazySum = 0;
        leaf = true;
    }
    Node (Node* left, Node* right) {
        height = 0;
        first = left->first;
        last = right->last;
        lazySum = 0;
        leaf = false;
    }

    void propagate(Node* left, Node* right) {
        if (left->leaf) {
            left->height += lazySum;
            left->first = left->height;
            left->last = left->height;
        } else {
            left->lazySum += lazySum;
            left->first += lazySum;
            left->last += lazySum;
        }
        if (right->leaf) {
            right->height += lazySum;
            right->first = right->height;
            right->last = right->height;
        } else {
            right->lazySum += lazySum;
            right->first += lazySum;
            right->last += lazySum;
        }
        lazySum = 0;
    }
};

int n;
int queries;
int input[MAX_N];

namespace SegmentTree {

    Node nodes[MAX_NODES];
    int indexes[MAX_N];

    // first call to namespace, builds the tree from input array
    Node* build(int index = 0, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start == end) {
            nodes[index] = Node(input[start]);
            indexes[start] = index;
            return &nodes[index];
        }

        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = (start + end) / 2;

        Node* left = build(leftIndex, start, mid);
        Node* right = build(rightIndex, mid + 1, end);

        nodes[index] = Node(left, right);
        indexes[start] = index;
        return &nodes[index];
    }

    // returns the first index such that values[index] >= value
    int lowerBound(int value, int index = 0, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start == end) {
            if (value > nodes[index].height) return start + 1;
            return start;
        }

        Node* current = &nodes[index];

        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = (start + end) / 2;

        Node* left = &nodes[leftIndex];
        Node* right = &nodes[rightIndex];

        current->propagate(left, right);

        if (value <= left->last) {
            return lowerBound(value, leftIndex, start, mid);
        } else {
            return lowerBound(value, rightIndex, mid + 1, end);
        }
    }

    // returns the number of values inside the range [min, max] (inclusive)
    int query(int min, int max) {
        int lower = lowerBound(min);
        int higher = lowerBound(max + 1);

        return higher - lower;
    }

    // internal return only
    // returns 1 if parent should increase the endpoint
    std::pair<int, int> updateRange(int lower, int higher, int index = 0, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (higher < lower) return pair(0, 0);

        if (start > higher || lower > end) return pair(0, 0);

        if (start == end) {
            nodes[index].height++;
            nodes[index].first++;
            nodes[index].last++;
            return pair(1, 1);
        }

        if (end <= start && end <= higher) {
            nodes[index].first++;
            nodes[index].last++;
            nodes[index].lazySum++;
            return pair(1, 1);
        }

        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = (start + end) / 2;

        std::pair<int, int> leftUpdate  = updateRange(lower, higher, leftIndex, start, mid);
        std::pair<int, int> rightUpdate = updateRange(lower, higher, rightIndex, mid + 1, end);

        if (leftUpdate.first == 1) {
            nodes[index].first++;
        }
        if (rightUpdate.second == 1) {
            nodes[index].last++;
        }
        return pair(leftUpdate.first, rightUpdate.second);
    }

    int getValue(int x, int index = 0, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start == end) return nodes[index].height;

        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = (start + end) / 2;

        nodes[index].propagate(&nodes[leftIndex], &nodes[rightIndex]);

        if (x <= mid) return getValue(x, leftIndex, start, mid);
        if (x >  mid) return getValue(x, rightIndex, mid + 1, end);
    }

    // adds 1 to the height of the shortest trees > minHeight, for a maximum of quantity trees
    void update(int quantity, int minHeight) {
        int startIndex = lowerBound(minHeight);
        if (startIndex >= n) return;
        int maxHeight = getValue(startIndex + quantity - 1);
        int maxStartIndex = lowerBound(maxHeight);
        int maxEndIndex = lowerBound(maxHeight + 1) - 1;

        updateRange(startIndex, maxStartIndex - 1);
        int updated = maxStartIndex - startIndex;
        int remaining = quantity - updated;
        updateRange(std::max(maxEndIndex - remaining + 1, maxStartIndex), maxEndIndex);

        debug("maxHeight: %d\n", maxHeight);
        debug("updated: %d\n", updated);
        debug("remaining: %d\n", remaining);
        debug("updateRange(%d, %d)\n", startIndex, maxStartIndex - 1);
        debug("updateRange(%d, %d)\n", maxEndIndex - remaining + 1, maxEndIndex);
    }

    void print(int index = 0, int start = 0, int end = -1) {
        if (end == -1) end = n - 1;

        if (start == end) {
            printf("%d, ", nodes[index].height);
            return;
        }

        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = (start + end) / 2;

        nodes[index].propagate(&nodes[leftIndex], &nodes[rightIndex]);

        print(leftIndex, start, mid);
        print(rightIndex, mid + 1, end);

        if (index == 0) printf("\n");
    }

}

int main() {

    scanf("%d %d", &n, &queries);

    for (int i = 0; i < n; i++) {
        scanf("%d", &input[i]);
    }

    std::sort(input, input + n);

    SegmentTree::build();

    // SegmentTree::print();

    for (int q = 0; q < queries; q++) {

        char c;
        int x, y;
        scanf(" %c %d %d", &c, &x, &y);

        if (c == 'F') {
            SegmentTree::update(x, y);
            // SegmentTree::print();
        } else if (c == 'C') {
            int answer = SegmentTree::query(x, y);
            printf("%d\n", answer);
        }

    }
}

Compilation message

grow.cpp: In function 'int SegmentTree::getValue(int, int, int, int)':
grow.cpp:182:5: warning: control reaches end of non-void function [-Wreturn-type]
  182 |     }
      |     ^
grow.cpp: In function 'int main()':
grow.cpp:228:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  228 |     scanf("%d %d", &n, &queries);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:231:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  231 |         scanf("%d", &input[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:244:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |         scanf(" %c %d %d", &c, &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 9556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8140 KB Output is correct
2 Correct 6 ms 8172 KB Output is correct
3 Correct 6 ms 8144 KB Output is correct
4 Correct 5 ms 8140 KB Output is correct
5 Correct 61 ms 9164 KB Output is correct
6 Correct 97 ms 9388 KB Output is correct
7 Correct 34 ms 8140 KB Output is correct
8 Correct 41 ms 8864 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 9440 KB Output is correct
2 Correct 258 ms 9472 KB Output is correct
3 Correct 47 ms 8204 KB Output is correct
4 Correct 52 ms 9116 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 9660 KB Output is correct
2 Correct 137 ms 9444 KB Output is correct
3 Correct 154 ms 8388 KB Output is correct
4 Correct 194 ms 9492 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1064 ms 9668 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 9768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1082 ms 9596 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1041 ms 9672 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 9928 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 402 ms 11312 KB Output is correct