AtCoder ABC183 D - Water Heater

問題

atcoder.jp

解法

答えは「どの時刻においても、「使用量≦上限」であるか?」です。
各時刻の使用量は「imos法」を用いると、高速に求められます。

imos法って?

imos法は、例えば「時刻iにおけるバスの乗客数」を求めるのに使われます。
「時刻A~Bの間、C人組がバスに乗る」というデータがいくつも与えられる場合、
「時刻AでC人増える(array[A] += C)」「時刻B+1でC人減る(array[B+1] -= C)」という形で配列に記録します。
全て記録した後に配列の累積和を取ると、array[i]には時刻iの乗客数が格納されています。
(時刻1, 2, 3, ... と累積和を求めていくことは、「ある時刻でx人乗り/ある時刻でy人降り…」を実際にシミュレーションしているのと同じことをしています。)

実装

import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int w = sc.nextInt();
        
        int[] start = new int[n];
        int[] end = new int[n];
        long[] p = new long[n];
        for(int i = 0; i < n; i++) {
            start[i] = sc.nextInt();
            end[i] = sc.nextInt();
            p[i] = sc.nextLong();
        }
        
        // sum[i]: 時刻iの使用量
        long[] sum = new long[200005];
        for (int i = 0; i < n; i++) {
            // 時刻start[i]で使用量がp[i]増える
            // 時刻end[i]で使用量がp[i]減る
            sum[start[i]] += p[i];
            sum[end[i]] -= p[i];
        }
        for (int i = 0; i < 200005 - 1; i++) {
            sum[i + 1] += sum[i];
        }
        
        boolean ok = true;
        for (int i = 0; i < 200005; i++) {
            if (sum[i] > w) ok = false;
        }
        
        if (ok) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}