[At Coder] Solve the ABC183 D problem with Ruby

The brown coder tried to solve the ABC183 D problem in Ruby.

problem

There is a $ 1 $ water heater that can supply $ W $ liters of hot water per minute. There are $ N $ people. The $ i $ th person plans to use $ P_i $ liters of water boiled in this water heater every minute between time $ S_i $ and $ T_i $ (excluding time $ T_i $). The hot water cools quickly and cannot be stored. Is it possible to supply hot water to everyone as planned?

Constraint

1 \leq N \leq 2 \times 10^5 0 \leq S_i \leq 2 \times 10^5 1 \leq W, P_i \leq 10^9 All inputs are integers

input

N　W S_1　T_1　P_1 ︙ S_N　T_N　P_N

Answer

nw = gets.chomp.split.map(&:to_i)
n = nw[0]
w = nw[1]

#An array that stores the amount of water used per hour
a = Array.new(200005, 0)

n.times do
    stp = gets.chomp.split.map(&:to_i)
    s = stp[0]
    t = stp[1]
    p = stp[2]

    #Preparation for "array to store cumulative sum"
    a[s] += p
    a[t] -= p
end

result = true

#Store cumulative sum
200001.times do |i|
    if a[i] > w
        result = false
        break
    end
    a[i+1] += a[i]
end

puts result ? "Yes" : "No"

Way of thinking

Use the cumulative sum. However, keep in mind that you will do it later, not from the beginning.

Prepare an array to store the amount of water used per hour
Increase or decrease the amount of water used only at the beginning and end of use
Calculate the cumulative sum of water consumption for each hour

Prepare an array to store the amount of water used per hour

Since it is $ T_i \ leq 2 \ times 10 ^ 5 $, prepare an array with $ 200001 $ or more elements.

Increase or decrease the amount of water used only at the beginning and end of use

As mentioned above, the point is not to calculate the cumulative sum at first. If you ask for it from the beginning, you will run out of execution time.

First of all, when entering information for $ N $ people, only increase or decrease the amount of water used at the beginning and end of use. Specifically, do as follows.

--Increase the amount of water used when you start using --Reduce the amount of water used at the end of use

Calculate the cumulative sum of water consumption for each hour

After that, we will calculate the cumulative sum as usual. It is OK if you judge whether it exceeds $ W $.

Impressions

I went to ask for the cumulative sum from the beginning, but I couldn't AC because the execution time was not enough. Crying Increase the amount of water used only at the beginning of use, and decrease it only at the end of use. I see, I feel like I had that hand.