Submission #2549555

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int dp[301][301][301];
bool did[301][301][301][3];
bool dont[301][301][301];
short cond[301][301];
ll mod = 1e9 + 7;

// #undef DEBUG
// #define DEBUG
/// {{{ DEBUG --- ///
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { if(&o == &cerr) { o << '{'; for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? ", " : ""); o << "}"; } else { for(size_t i = 0; i < v.size(); i++) o << v[i] << (i + 1 != v.size() ? " " : ""); } return o; }
#ifdef DEBUG
#define dump(...) (cerr<<"["<<__LINE__<< "] "<<#__VA_ARGS__<<" = "<<make_tuple(__VA_ARGS__)<<"\n")
template<int n, class...T> typename enable_if<(n>=sizeof...(T))>::type _ot(ostream &, tuple<T...> const &){}
template<int n, class...T> typename enable_if<(n< sizeof...(T))>::type _ot(ostream & os, tuple<T...> const & t){ os << (n==0?"":", ") << get<n>(t); _ot<n+1>(os, t); }
template<class...T> ostream & operator<<(ostream &o, tuple<T...> const &t){ o << "("; _ot<0>(o, t); o << ")"; return o; }
#else
#define dump(...) (0)
#endif
/// }}}--- ///

void calc(int k, int r, int g, int b, int t, int r2, int g2, int b2) {
  if(did[r][g][b][t]) return;
  did[r][g][b][t] = 1;
  dp[r2][g2][b2] = ((ll) dp[r2][g2][b2] + dp[r][g][b]) % mod;
}

void calc0(int k, int r, int g, int b) {
  if(dp[r][g][b] == 0) return;
  calc(k, r, g, b, 0, k, g, b);
  calc(k, r, g, b, 1, r, k, b);
  calc(k, r, g, b, 2, r, g, k);
}

int solve() {
  ios::sync_with_stdio(false), cin.tie(0);
  int n, m; cin >> n >> m;
  for(int i = 0; i < m; i++) {
    int l, r, x; cin >> l >> r >> x;
    if(cond[l][r] != 0 && cond[l][r] != x) return 0;
    cond[l][r] = x;
    for(int G = 0; G < r; G++) for(int R = 0; R <= G; R++) {
      if(G == R && R != 0) continue;
      switch(x) {
        case 1: if(G >= l) dont[R][G][r] = 1; break;
        case 2: if(R >= l || l > G) dont[R][G][r] = 1; break;
        case 3: if(l > R) dont[R][G][r] = 1; break;
      }
    }
  }
  dp[0][0][0] = 1;
  for(int k = 1; k <= n; k++) {
    int B = k - 1;
    for(int G = 0; G <= B; G++) {
      if(B == G && G != 0) continue;
      for(int R = 0; R <= G; R++) {
        if(G == R && R != 0) continue;
        if(dont[R][G][k]) continue;
        calc0(k, R, G, B);
        calc0(k, R, B, G);
        calc0(k, G, R, B);
        calc0(k, G, B, R);
        calc0(k, B, R, G);
        calc0(k, B, G, R);
      }
    }
  }
  ll res = 0;
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      res += dp[i][j][n];
      res += dp[i][n][j];
      res += dp[n][i][j];
    }
  }
  res %= mod;
  return res;
}

int main() {
  cout << solve() << endl;
}

Submission Info

Judge Result