hackercup2013-r1-dead-pixels.cpp

#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <set>
#include <map>
#include <algorithm>
#include <cassert>
#include <cmath>

using namespace std;

typedef long long int int64;
typedef vector<int> VI;
#define REP(i,a,b) for (int i=int(a); i<int(b); ++i)
void unittest();

#define PX(p) (p.first)
#define PY(p) (p.second)
int W, H, P, Q, N, X, Y, a, b, c, d;
int ww, hh;

typedef pair<int, int> PII;
typedef vector<PII> VP;
typedef multiset<int> MSI;
VP enters, leaves;

MSI curp;
int curi;
int ans;

const int NINF=-99999;

void dmp(VP& ps) {
  REP(i, 0, ps.size()) {
    PII& p = ps[i];
    printf("%d, %d\n", PX(p), PY(p));
  }
}

void add(VP& ps, PII p) {
  PX(p) = max(PX(p), 0);
  PX(p) = min(PX(p), ww);
  // PY(p) = max(PY(p), 0);
  // PY(p) = min(PY(p), hh);
  ps.push_back(p);
}

void gen() {
  int x=X, y=Y;
  REP(i, 0, N) {
    add(enters, PII(x-P+1, y-Q+1));
    add(leaves, PII(x+1, y-Q+1));

    // printf("Gen: %d, %d\n", x, y);

    // enters.push_back(PII(x-W+1, y-H+1));
    // leaves.push_back(PII(x, y));

    int ox=x, oy=y;
    x = (ox*a + oy*b + 1) % W;
    y = (ox*c + oy*d + 1) % H;
  }
  sort(enters.begin(), enters.end());
  sort(leaves.begin(), leaves.end());
  // printf("WW, HH: %d, %d(%d, %d)\n", ww, hh, P, Q);
  // dmp(enters); printf("-----\n"); dmp(leaves);
}

void bound(int y, int& start, int& finish) {
  start = y;
  finish = y+Q;

  MSI::iterator it = curp.lower_bound(y);
  if (it!=curp.end()) {
    int ry = *it;
    if (ry<finish)
      finish = ry;
  }
  --it;
  {
    int ry = *it;
    if (ry+Q>start)
      start = ry+Q;
  }
  start = max(start, 0);
  finish = min(finish, hh);
  if (start>finish) finish=start;
  // printf("Bound %d, %d(origin: %d, %d)\n", start, finish, y, y+Q);
}

void cremove(int x, int y) {
  MSI::iterator it = curp.find(y);
  assert(it!=curp.end());
  curp.erase(it);

  int start, finish;
  bound(y, start, finish);

  curi += (finish-start);
  // printf("Leave %d, %d (%d, %d)-> %d\n", x, y, start, finish, curi);
}

void cinsert(int x, int y) {
  int start, finish;
  bound(y, start, finish);

  curi -= (finish-start);

  curp.insert(y);
  // printf("Enter %d, %d (%d, %d)-> %d\n", x, y, start, finish, curi);
}

void solve(int caseNum) {
  scanf("%d %d %d %d %d %d %d %d %d %d %d", &W, &H, &P, &Q, &N, &X, &Y, &a, &b, &c, &d);
  // printf("%d %d %d %d %d %d %d %d %d %d %d\n", W, H, P, Q, N, X, Y, a, b, c, d);
  ww = W-P+1;
  hh = H-Q+1;

  enters.clear();
  leaves.clear();

  gen();

  curp.clear();
  curp.insert(NINF);
  curi = hh;
  ans = 0;
  // printf("Initial curi=%d\n", curi);

  VP::iterator eit = enters.begin();
  VP::iterator lit = leaves.begin();
  REP(x, 0, ww+1) {
    while(eit!=enters.end()) {
      const PII& p = *eit;
      if (PX(p)!=x) break;
      cinsert(PX(p), PY(p));
      ++eit;
    }
    while(lit!=leaves.end()) {
      const PII& p = *lit;
      if (PX(p)!=x) break;
      cremove(PX(p), PY(p));
      ++lit;
    }
    if (x!=ww) {
      // printf("X=%d, curi=%d\n", x, curi);
      ans += curi;
    }
  }
  assert(curp.size()==1);
  assert(curi==hh);

  printf("Case #%d: %d\n", caseNum, ans);
}

int main() {
  unittest();
  int caseCount;
  cin>>caseCount;
  REP(i, 1, caseCount+1)
    solve(i);

  return 0;
}

void unittest() {
}