patterncppMinor

Time Limit Exceeded with Segment Tree data structure

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

withlimitdatatimesegmentstructureexceededtree

Problem

I am trying to solve this problem

Chef Ceil has some matchsticks in his kitchen.

Detail of matchsticks:

There are N matchsticks in total. They are numbered from to 0 to N-1
inclusive. All matchsticks have same length. But they may have
different rates of burning. For ith matchstick, we denote bi as the
time required for that matchstick to completely burn-down if lighted
at one end. The matchsticks have uniform rate of burning. If lighted
at both ends simultaneously, the matchstick will take only half of the
original time to burn down.

Arrangement:

He ties rear end of the all
the matchsticks together at one point and the front end is kept free.
The matchstick numbered i is adjacent to matchstick numbered i+1 for
all 0

\$O(4Qlog(N))\$ since I run 4 Range_Min(Max)_querys for each query \$Q\$.

Everything seems to be working but I still don"t understand why I am getting TLE.

Solution

You have written your code in a way that makes it extremely difficult to understand, and almost impossible without the problem statement nearby. What is Q? Well, we have to return to the statement of the problem to find out it is the number of queries. Likewise, you use typedefs and macros that obfuscate the meaning of your code, and you use globals for reasons I don't understand.

After some study, I have determined that your algorithm is as follows:

Read in the parameters of the problem.

Construct a segment tree that supports queries of the form: What is the burn time of the shortest match stick in the range [i, j]?

Construct a segment tree that supports queries of the form: What is the burn time of the longest match stick in the range [i, j]?

Read in a query's parameters L, R.

Determine the burn time of the shortest match stick in the range [L, R] (min).

Determine the burn time of the longest match stick in the range [0, L-1] (max1).

Determine the burn time of the longest match stick in the range [L, R] (max2 -- this requires special treatment as it burns twice as fast after min time has elapsed).

Determine the burn time of the longest match stick in the range [R+1, N] (max3).

Print min + max(max1, max2, max3).

Repeat 4-9 while queries remain.

Let me offer an alternate version of your code that follows the same algorithm, with commentary interspersed:

#include 
#include 
#include 
#include 
#include 
#include 
#include 

namespace chef_ceil {

I have chosen to use iostream instead of cstdio; we're writing C++, not C. Also, I've omitted using namespace std; (see the top two answers of this SO question, and all of your macros, typedefs, and global variables.

I have also put everything into a namespace.

/**
 * A data structure that can answer queries of the form "what is the minimum
 * value between indexes L and R?" With Comp=std::greater, finds maxima instead.
 *
 * Requires O(N) storage for an input with N values.
 */
template >
class SegmentTree {
  public:
    /**
     * Constructs a SegmentTree over the given values.
     *
     * Requires O(N) time to construct.
     */
    static SegmentTree New(const std::vector& ts, Comp comp=Comp());

    /**
     * Find the smallest (largest) value that has an index between l and r inclusive.
     *
     * Requires O(log N) time.
     */
    T query(std::size_t l, std::size_t r) const;

    std::size_t num_values() const { return num_values_; }

  private:
    SegmentTree(std::vector&& nodes, Comp comp, std::size_t num_values)
      : nodes_(std::move(nodes)), comp_(comp), num_values_(num_values) {}

    T query_helper(std::size_t l, std::size_t r, std::size_t node,
                   std::size_t b, std::size_t e) const;

    std::vector nodes_;
    Comp comp_;
    std::size_t num_values_;

};

C++ is an object-oriented language; it is sensible to define a class that encapsulates behavior instead of throwing the behavior of this data structure into various parts of the code.

namespace {
std::size_t num_nodes(std::size_t num_leaves) {
  // Round up to the nearest power of two to get the number of leaves in the
  // complete binary tree, then multiply by 2 (normally you would subtract 1,
  // but we leave node 0 empty and use node 1 as the root).
  return std::lrint(std::exp2(1 + std::ceil(std::log2(num_leaves))));
}

Note the comment explaining why I'm using such a complicated formula.

```
template
T build_from_node(std::vector& nodes, const std::vector& ts, Comp comp,
std::size_t node, std::size_t l, std::size_t r) {
if (l == r) {
nodes[node] = ts[l];
return ts[l];
}
int left_child = 2 * node;
int right_child = 2 * node + 1;

const T left_value = build_from_node(nodes, ts, comp, left_child, l, (l + r) / 2);
const T right_value = build_from_node(nodes, ts, comp, right_child, (l + r) / 2 + 1, r);
nodes[node] = comp(left_value, right_value) ? left_value : right_value;
return nodes[node];
}
} // namespace

template
SegmentTree SegmentTree::New(const std::vector& ts, Comp comp) {
std::vector nodes;
nodes.reserve(num_nodes(ts.size()));
build_from_node(nodes, ts, comp, 1, 0, ts.size() - 1);

return SegmentTree(std::move(nodes), comp, ts.size());
}

template
T SegmentTree::query(std::size_t l, std::size_t r) const {
if (l > r || l = num_values_) throw std::out_of_range("bad query");

return query_helper(l, r, 1, 0, num_values_ - 1);
}

template
T SegmentTree::query_helper(std::size_t l, std::size_t r, std::size_t node,
std::size_t b, std::size_t e) const {
if (l mid) // left child is irrelevant
return query_helper(l, r, right_child, mid + 1, e);
if (r <= mid) // right child is irrelevant
return query_helper(l, r, left_child, b, mid);

const auto left_value = query_helper(l, r, left_child, b, mid);
const auto right_value = query_helper(l, r, right_child, mid + 1, e);
return comp_(left_value,

Code Snippets

#include <algorithm>
#include <cmath>
#include <functional>
#include <iostream>
#include <iterator>
#include <utility>
#include <vector>

namespace chef_ceil {

/**
 * A data structure that can answer queries of the form "what is the minimum
 * value between indexes L and R?" With Comp=std::greater<T>, finds maxima instead.
 *
 * Requires O(N) storage for an input with N values.
 */
template <typename T, typename Comp=std::less<T>>
class SegmentTree {
  public:
    /**
     * Constructs a SegmentTree over the given values.
     *
     * Requires O(N) time to construct.
     */
    static SegmentTree New(const std::vector<T>& ts, Comp comp=Comp());

    /**
     * Find the smallest (largest) value that has an index between l and r inclusive.
     *
     * Requires O(log N) time.
     */
    T query(std::size_t l, std::size_t r) const;

    std::size_t num_values() const { return num_values_; }

  private:
    SegmentTree(std::vector<T>&& nodes, Comp comp, std::size_t num_values)
      : nodes_(std::move(nodes)), comp_(comp), num_values_(num_values) {}

    T query_helper(std::size_t l, std::size_t r, std::size_t node,
                   std::size_t b, std::size_t e) const;

    std::vector<T> nodes_;
    Comp comp_;
    std::size_t num_values_;

};

namespace {
std::size_t num_nodes(std::size_t num_leaves) {
  // Round up to the nearest power of two to get the number of leaves in the
  // complete binary tree, then multiply by 2 (normally you would subtract 1,
  // but we leave node 0 empty and use node 1 as the root).
  return std::lrint(std::exp2(1 + std::ceil(std::log2(num_leaves))));
}

template <typename T, typename Comp>
T build_from_node(std::vector<T>& nodes, const std::vector<T>& ts, Comp comp,
                  std::size_t node, std::size_t l, std::size_t r) {
  if (l == r) {
    nodes[node] = ts[l];
    return ts[l];
  }
  int left_child = 2 * node;
  int right_child = 2 * node + 1;

  const T left_value = build_from_node(nodes, ts, comp, left_child, l, (l + r) / 2);
  const T right_value = build_from_node(nodes, ts, comp, right_child, (l + r) / 2 + 1, r);
  nodes[node] = comp(left_value, right_value) ? left_value : right_value;
  return nodes[node];
}
}  // namespace

template <typename T, typename Comp>
SegmentTree<T, Comp> SegmentTree<T, Comp>::New(const std::vector<T>& ts, Comp comp) {
  std::vector<T> nodes;
  nodes.reserve(num_nodes(ts.size()));
  build_from_node(nodes, ts, comp, 1, 0, ts.size() - 1);

  return SegmentTree(std::move(nodes), comp, ts.size());
}

template <typename T, typename Comp>
T SegmentTree<T, Comp>::query(std::size_t l, std::size_t r) const {
  if (l > r || l < 0 || r >= num_values_) throw std::out_of_range("bad query");

  return query_helper(l, r, 1, 0, num_values_ - 1);
}

template <typename T, typename Comp>
T SegmentTree<T, Comp>::query_helper(std::size_t l, std::size_t r, std::size_t node,
                                     std::size_t b, std::size_t e) const {
  if (l <= b && e <= r) return nodes_[node];

  const auto left_child = 2 * node;
  const auto right_child = 2 * node + 1;
  const auto mid = (b + e) / 2;

  if (l > mid)  // left child is irrelevant
    return query_helper(l, r, right_child, mid + 1, e);
  if (r <= mid)  // right child is irrelevant
    return query_helper(l, r, left_child, b, mid);

  const auto left_value = query_helper(l, r, left_child, b, mid);
  const auto right_value = query_helper(l, r, right_child, mid + 1, e);
  return comp_(left_value, right_value) ? left_value : right_value;
}

namespace {
std::vector<int> read_match_lengths(std::istream& is) {
  int num_matches;
  is >> num_matches;
  std::vector<int> match_lengths;
  match_lengths.reserve(num_matches);
  std::copy_n(std::istream_iterator<int>(is), num_matches, std::back_inserter(match_lengths));
  return match_lengths;
}

int compute_burn_time_for_range(const SegmentTree<int>& min_tree,
                                const SegmentTree<int, std::greater<int>>& max_tree,
                                int l, int r) {
  const int light_time = min_tree.query(l, r);
  const int left_burn_time = l > 0 ? max_tree.query(0, l - 1) : 0;
  const int right_burn_time = r + 1 < max_tree.num_values()
                              ? max_tree.query(r + 1, max_tree.num_values() - 1)
                              : 0;
  // The amount of time it takes to burn the longest match in the lit range
  // *after* all the match rears are lit is (b_i - light_time) / 2.
  const int lit_burn_time = (max_tree.query(l, r) - light_time) / 2;

  return light_time + std::max({left_burn_time, right_burn_time, lit_burn_time});
}
}   // namespace
}  // namespace chef_ceil

Context

StackExchange Code Review Q#55866, answer score: 6

Revisions (0)

No revisions yet.