Artifact Content
Not logged in

Artifact c220b48258d1e6335347484fe8dd5d23331c239f


#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long LL;

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 {
		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() ) {
				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;
	}
};

// BEGIN CUT HERE
#include <ctime>
double start_time;string timer() { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }

template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
int verify_case(const int &Expected, const int &Received) { if (Expected == Received) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } return 0;}

template<int N> struct Case_ { Case_(){start_time=clock();} };
char Test_(...);
int Test_(Case_<0>) {
	int N = 5; 
	int M = 1; 
	int X0 = 2; 
	int A = 0; 
	int B = 0; 
	int Y0 = 2; 
	int C = 0; 
	int D = 0; 
	int RetVal = 4; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<1>) {
	int N = 4; 
	int M = 4; 
	int X0 = 0; 
	int A = 1; 
	int B = 1; 
	int Y0 = 0; 
	int C = 1; 
	int D = 1; 
	int RetVal = 6; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<2>) {
	int N = 1; 
	int M = 1000000; 
	int X0 = 1; 
	int A = 2; 
	int B = 3; 
	int Y0 = 1; 
	int C = 4; 
	int D = 7; 
	int RetVal = 0; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<3>) {
	int N = 10; 
	int M = 20; 
	int X0 = 4; 
	int A = 76; 
	int B = 2; 
	int Y0 = 6; 
	int C = 2; 
	int D = 43; 
	int RetVal = 12; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<4>) {
	int N = 1999; 
	int M = 4000000; 
	int X0 = 1000; 
	int A = 1; 
	int B = 1; 
	int Y0 = 0; 
	int C = 1; 
	int D = 1; 
	int RetVal = 1002995; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
int Test_(Case_<5>) {
	int N = 2000; 
	int M = 4000000; 
	int X0 = 1500; 
	int A = 1; 
	int B = 1; 
	int Y0 = 500; 
	int C = 1; 
	int D = 1; 
	int RetVal = 1003997; 
	return verify_case(RetVal, PerfectRectangles().numberOfRectangles(N, M, X0, A, B, Y0, C, D)); }
template<int N> void Run_() { cerr << "Test Case #" << N << "..." << flush; Test_(Case_<N>()); Run_<sizeof(Test_(Case_<N+1>()))==1 ? -1 : N+1>(); }
template<> void Run_<-1>() {}
int main() { Run_<0>(); }
// END CUT HERE