leetcode-go/poj/2373.dividing-the-path/main.cc

#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int INF = 1 << 30;
const int MAXL = 1000000;
const int MAXN = 1000;
int dp[MAXL + 1];
int has_cow[MAXL + 1];
int N, L, A, B;

// If f(x) means the min cnt of sprinklers to cover [0...x], then we have
// f(x) = INF, if x is odd
//      = INF, if x < 2A
//      = INF, if has_cow[x]
//      = 1, if 2A <= x <= 2B and !has_cow[x]
//      = min{f(y): x - 2B <= y <= x - 2A} + 1, if 2B < x and !has_cow[y]

struct Fx {
  int x;
  int f;
  Fx(int x = 0, int f = 0) : x(x), f(f) {}
  bool operator<(const Fx &that) const { return this->f > that.f; }
};

int main() {
  scanf("%d %d %d %d", &N, &L, &A, &B);
  A <<= 1, B <<= 1;
  for (int i = 0; i < N; i++) {
    int s, e;
    scanf("%d %d", &s, &e);
    has_cow[s + 1]++;
    has_cow[e]--;
  }
  for (int i = 0, cows = 0; i <= L; i++) {
    dp[i] = INF;
    cows += has_cow[i];
    has_cow[i] = 0 < cows;
  }
  priority_queue<Fx> pq;
  for (int x = A; x <= B; x += 2) {
    if (!has_cow[x]) {
      dp[x] = 1;
      // Ensure that for each x, the y in pq has y <= x - A
      if (x <= B + 2 - A) pq.push(Fx{x, 1});
    }
  }
  for (int x = B + 2; x <= L; x += 2) {
    if (!has_cow[x]) {
      Fx fx;
      while (!pq.empty()) {
        fx = pq.top();
        if (fx.x < x - B)
          pq.pop();
        else
          break;
      }
      if (!pq.empty()) dp[x] = fx.f + 1;
    }
    // Push next Fx to queue.
    if (dp[x + 2 - A] != INF) pq.push(Fx(x + 2 - A, dp[x + 2 - A]));
  }
  int cnt = dp[L] == INF ? -1 : dp[L];
  printf("%d\n", cnt);
  return 0;
}