[Practice Mode] HackerCup-2013 Round-1 :: DeadPixel

Lession-11: General approach is always successful. For this problem,Just imagine how 'ROBO't Scans the book.
i.e. From left to right or top to bottom or right to left or bottom to top.
If you don't know yet, watch ROBO Movie :P ...Seriously.

Lession-12: Set is another beautiful STL Container that you need to know.

Lession-13: If you want to make use of sort at the best, I recommend not to use any comparator function. Believe it or not It runs out of memory if you use any comparator function.

Lession-14: Love C++ More and More, especially when there is no need to write Deque or Queue or Hashmap or Multimap or Set and other Standard function. Of course there are many languages which are having rich libraries but C++ has its own mark. May be my love towards pointers :P is coming out in dis way :D.

Lession-15: Jintak tak Jintak...Jinta...Jinta tha Thahhh...!! Working on Other problems.

// =====================================================================================
//       Filename:  deadPixel.cpp
//    Description:  
//        Created:  02/07/2013 04:06:57 PM
//         Author:  BrOkEN@!
// =====================================================================================

#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iterator>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<cstdio>
#include<cstdlib>
#include<cstddef>
#include<cstring>
#include<cctype>
#include<cmath>
#include<cassert>
#include<climits>
#include<ctime>

#define TIMER 1
#define MAX 40000

#define FOR(i,a,b) for(typeof(a) i=(a); i <= (b); i++) 
#define FOREACH(it,a) for(typeof(a.begin()) it=a.begin(); it != a.end(); ++it) 

using namespace std;

typedef pair<int,int> PI;
typedef vector<PI> VI;
typedef deque<PI> DQ;
typedef long long LL;

int W=0,H=0,P=0,Q=0,N=0,X=0,Y=0,a=0,b=0,c=0,d=0;
VI v;
DQ xs;


int getPossible(){
	set<int> k;
	FOREACH(i,xs){k.insert((*i).second);}
	k.insert(H);	
	
	int d=0,pre=-1;
	FOREACH(i,k){
		if((*i)-pre-1 >= Q){
			d+=((*i)-pre-1)-Q+1;
		};
		pre= *i;
	}

	return d;
	
}

LL solve(){
	v.clear();

	v.push_back(PI(X,Y));
	FOR(i,1,N-1){
		v.push_back(PI((v[i-1].first * a + v[i-1].second * b + 1) % W ,(v[i-1].first * c + v[i-1].second * d + 1) % H));	
	}	
	
	sort(v.begin(),v.end());

	LL sum=0LL;
	xs.clear();
	
	VI::iterator it=v.begin();
	FOR(d,0,W-P){
		while(!xs.empty() && ((xs.front()).first<d)){
			xs.pop_front();
		}

		while(it!=v.end() && (*it).first<=P-1+d){
			if(	(xs.empty()) || 
				((xs.back()).first<(*it).first) || 
				(((xs.back()).first==(*it).first) && ((xs.back()).second<(*it).second))
			){
				xs.push_back(*it);
			}
			++it;
		}
		sum+=(LL)getPossible();
	}
	return sum;
}

int main(){
#ifdef TIMER
	clock_t t=clock();
#endif
	int T=0;
	scanf("%d",&T);
	FOR(t,1,T){
		scanf("%d %d %d	%d %d %d %d %d %d %d %d",&W,&H,&P,&Q,&N,&X,&Y,&a,&b,&c,&d);
		printf("Case #%d: %lld\n",t,solve());
	}

#ifdef TIMER
	printf ("It took %f seconds to run.\n",((float)(clock()-t))/CLOCKS_PER_SEC);
#endif	
	return 0;
}