Keen Tree Design | MatCom Online Grader

The 2024 ICPC Caribbean Finals (Qualifier) - Real Contest

Ended

Overview
Problems
Standing
Submissions
Submit
Clarifications
Virtual participation

Register

Are you sure you want to participate in this contest ? If you select a team then virtual participation for other team members will be disabled. So, pick one if and only if your teammates are ready to compete with you.

K - Keen Tree Design

Languages: C, C++, Java, Python, Kotlin

Time & Memory limits: (details)

<div style="text-align: justify">
You need to design an optimal segment tree to minimize the cost of performing a set of given queries.

**Segment Tree Definition**

A segment tree is a binary tree structure used to efficiently handle range queries on an array. Each node in the segment tree represents a segment with a $start$ and $end$ position such that $start \leq end$. The segments are defined as follows:

1. **Leaf Nodes**: A segment is a leaf node if $start = end$. This node corresponds to a single element in the original array and has no children.
2. **Internal Nodes**: A segment is an internal node if $start < end$. Each internal node has two children:
    - **Left Child**: Represents the left half of the segment.
    - **Right Child**: Represents the right half of the segment.

For an internal node with segment $[start, end]$, we define a pivot position such that $start \leq pivot \leq end$. The segment is split as follows:
- The left child has the range $[start, pivot - 1]$.
- The right child has the range $[pivot, end]$.

**Segment Tree Usage**

A segment tree is useful for efficiently combining consecutive values in an array using an associative operation, such as sum, minimum, or maximum. Each node in the tree stores the combination of all values in its segment. Given a query to combine all values in a subrange $[l, r]$, the following strategy is used:

```python
class Segment:
    left: Segment | None  # Left child of the current segment
    right: Segment | None  # Right child of the current segment
    value: Value           # Combined value of the current segment
    start: int             # Start position of the segment
    pivot: int | None      # Pivot position that splits the segment
    end: int               # End position of the segment

def query(segment: Segment, l: int, r: int) -> Value:
    # Base case: If the query range completely covers the current segment
    if l <= segment.start and segment.end <= r:
        return segment.value

# If the query range falls entirely within the left child
    if r <= segment.pivot:
        return query(segment.left, l, r)

# If the query range falls entirely within the right child
    if segment.pivot < l:
        return query(segment.right, l, r)

# If the query range overlaps both children, combine the results
    left_value = query(segment.left, l, r)
    right_value = query(segment.right, l, r)

value = combine(left_value, right_value)
    return value
```

**Query Costs**

- **Query Cost ($a$)**: Each time the `query` function is called, it incurs a cost of $a$.
- **Combine Cost ($b$)**: Each time two segments are combined using the `combine` function, it incurs a cost of $b$.

**Objective**

You are given the distribution of all queries that will be performed on the segment tree. Your task is to find an optimal segment tree structure that minimizes the total cost of executing all queries.

Input