Submission #2240887

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

using int64 = long long;

const int mod = 1e9 + 7;

int main() {
  int N, M;
  int S[200], T[200];
  vector< int > vs;

  cin >> N >> M;
  for(int i = 0; i < M; i++) {
    cin >> S[i] >> T[i];
    vs.emplace_back(S[i]);
    vs.emplace_back(T[i]);
  }
  vs.emplace_back(1);
  vs.emplace_back(N);
  sort(begin(vs), end(vs));
  vs.erase(unique(begin(vs), end(vs)), end(vs));
  for(int i = 0; i < M; i++) {
    S[i] = lower_bound(begin(vs), end(vs), S[i]) - begin(vs);
    T[i] = lower_bound(begin(vs), end(vs), T[i]) - begin(vs);
  }

  vector< int > ev[403];
  for(int i = 0; i < M; i++) {
    ev[S[i]].emplace_back(T[i]);
  }
  bool isex[403] = {};
  for(int i = 0; i < vs.size() - 1; i++) {
    isex[i] = (vs[i] + 1 == vs[i + 1]);
  }
  isex[vs.size() - 1] = true;

  vector< vector< int > > dp(vs.size() + 1, vector< int >(vs.size() + 1));
  dp[0][0] = 1; // i, j)までカバー済み
  for(int i = 0; i < vs.size(); i++) {
    for(auto &v : ev[i]) {
      int nxt = v + isex[v];
      auto dp2 = dp;
      for(int j = i; j <= vs.size(); j++) {
        for(int k = i; k <= vs.size(); k++) {
          if(nxt <= j && nxt <= k) {
            (dp2[j][k] += dp[j][k]) %= mod;
          } else if(j < nxt && k < nxt) {
            if(j > k) (dp2[j][nxt] += dp[j][k]) %= mod;
            else (dp2[nxt][k] += dp[j][k]) %= mod;
          } else if(nxt <= j) {
            (dp2[j][max(nxt, k)] += dp[j][k]) %= mod;
          } else {
            (dp2[max(nxt, j)][k] += dp[j][k]) %= mod;
          }
        }
      }
      dp.swap(dp2);
    }
  }
  cout << dp.back().back() << endl;
}

Submission Info

Judge Result