cafelier@SRM

SRM431 1000

あとで | 11:15 |

あまりの美しくなさに死にそう。RMQなしで書けますよねこれ多分。まあいいや

template<typename T>
struct RMQ
{
  vector< vector<int> > rm;
  T*  d;
  int n;

  RMQ( T* d, int n ) : d(d), n(n) {
    rm.push_back( vector<int>(n) );
    for(int x=0; x<n; ++x)
      rm[0][x] = x;
    for(int k=1; (1<<k)<=n; ++k) {
      rm.push_back( rm[k-1] );
      for(int x=0; x+(1<<k-1)<n; ++x)
        if( d[rm[k][x]] > d[rm[k-1][x + (1<<k-1)]] )
          rm[k][x] = rm[k-1][x + (1<<k-1)];
    }
  }

  int operator()(int L, int R) const { // d[L]..d[R] (inclusive) の最小値の最左インデックスを返す
    int k=0;
    for(; L+(1<<k) < R-(1<<k)+1; ++k) {}
    LL i = rm[k][L];
    LL j = rm[k][R-(1<<k)+1];
    return (d[i]<=d[j] ? i : j);
  }

  vector<int> all(int L, int R) const { // 同、全列挙
    vector<int> ans;
    int minValue = d[(*this)(L, R)];
    while( L <= R ) {
      int C = (*this)(L, R);
      if( minValue < d[C] )
        break;
      ans.push_back(C);
      L = C+1;
    }
    return ans;
  }
};

int B[2048][2048];
int U[2048][2048];
int D[2048][2048];

class PerfectRectangles
{
public:
  int numberOfRectangles(int N, int M, int X0, int A, int _B, int Y0, int C, int _D) 
  {
    // input
    int x=X0%N, y=Y0%N;
    memset(B, 0, sizeof(B));
    for(int i=0; i<M; ++i) {
      B[x][y] = 1;
      x = (x*A+_B)%N;
      y = (y*C+_D)%N;
    }

    // up (上に何マス進んだら黒マスがあるか)
    for(int y=0; y<N; ++y)
      for(int x=0; x<N; ++x)
        U[y][x] = (B[y][x] ? 0 : y==0 ? 1 : U[y-1][x]+1);

    // down (下に何マス進んだら黒マスがあるか)
    for(int y=N-1; y>=0; --y)
      for(int x=0; x<N; ++x)
        D[y][x] = (B[y][x] ? 0 : y==N-1 ? 1 : D[y+1][x]+1);

    // solve
    int cnt = 0;
    for(int y=0; y<N; ++y) {
      RMQ<int> rmU(U[y], N);
      RMQ<int> rmD(D[y], N);

      stack< pair<int,int> > S;
      S.push( make_pair(0, N-1) );
      while( !S.empty() ) {
        // RMQによる再帰探索。[y][L]から[y][R]までを下辺とする長方形は取れるか
        int L = S.top().first;
        int R = S.top().second;
        S.pop();

        int d = rmD(L,R);
        if( D[y][d] == 1 )
          ++cnt; // すぐ下に黒マスがある場合、下辺になれる
        if( D[y][d] <= 1 ) {
          vector<int> m = rmU.all(L, R);
          m.push_back(R+1);
          for(int i=0; i<m.size(); L=m[i++]+1)
            if( L <= m[i]-1 )
              S.push( make_pair(L, m[i]-1) ); // 上に伸ばせる限界の高さで分割
        }
      }
    }
    return cnt;
  }
};