SRM681 div1 easy FleetFunding

考えたこと

• つくる数を決め打ったときにそれを実現できるかについて単調性がありそうなのでにぶたんができそう
• 二分探索部分でO(log(nm))
• 判定部分をどうすればいいか
• 区間と言われたので終端でソートする
• 終端が遅いものをできるだけ残しておくと後半にも使えてうれしい
• 終端が早いものから順番に消費していく貪欲で判定ができそう
• O(mn)で判定できるので問題なさそう

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

class FleetFunding {
   public:
   int maxShips(int m, vector <int> k, vector <int> a, vector <int> b)
  {
    int n = k.size();
    VVI v;
    REP(i, n) v.PB({b[i], a[i], k[i]});
    sort(ALL(v));

    auto check = [&](int mid) -> bool {
      VVI vec = v;
      FOR(i, 1, m+1) {
        int cnt = mid;
        REP(j, n) {
          if(vec[j][1] <= i && i <= vec[j][0]) {
            if(cnt >= vec[j][2]) cnt -= vec[j][2], vec[j][2] = 0;
            else vec[j][2] -= cnt, cnt = 0;
          }
        }
        if(cnt != 0) return false;
      }
      return true;
    };

    int lb=0, ub=5e7+10;
    while(ub-lb>1) {
      int mid = (lb+ub)/2;
      // cout << lb << " " << mid << " " << ub << endl;
      if(check(mid)) {
        lb = mid;
      } else {
        ub = mid;
      }
    }

    return lb;
  }
};