Zenn
💬

ABC 183 | D - Water Heater

2020/11/16に公開
競プロ
いもす法
tech

問題

考えたこと

いもす法の典型のような問題である。

以下は入力例1の図である。

区間すべてを配列にして足すとTLEになるのでS_iとT_iをイベントの開始(増加)と終了(減少)と捉えて配列に格納し順番にその時点でのお湯の量を記録し比較すればいい。
今回は[S_i, T_i)までお湯を使うので同じ時間の場合にお湯を使う人のイベントを消化する前にお湯を使い終わった人の計算をする必要がある。

コード

実装時のTips

  • vector<pair<ll,ll>>のソートはpairのfirst、secondの順番にソートしてくれるのでsecondがマイナスの場合はプラスの場合より前にくる。よって最初に引くことができるので減少の閉区間に対応できる。
#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n, w;
  cin >> n >> w;
  vector<pair<ll, ll>> event;
  for (int i = 0; i < n; i++) {
    ll s, t, p;
    cin >> s >> t >> p;
    event.push_back({s, p});
    event.push_back({t, -p});
  }
  sort(event.begin(), event.end());
  ll cur = 0;
  for (auto [time, value] : event) {
    cur += value;
    if (cur > w) {
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
}

参考

Discussion