main4.cc

#include <iostream>
#include <vector>
#include <algorithm>
#include <thread>
#include <mutex>

using namespace std;

mutex m;

void solve(int *r) {
  int W, H, P, Q, N, X, Y, a, b, c, d;

  m.lock();
  cin >> W >> H >> P >> Q >> N >> X >> Y >> a >> b >> c >> d;
  m.unlock();

  vector<int> x, y;
  x.push_back(X);
  y.push_back(Y);
  for (int i = 1; i < N; i++) {
    int xx = ((x.back() * a) + (y.back() * b) + 1) % W;
    int yy = ((x.back() * c) + (y.back() * d) + 1) % H;
    x.push_back(xx);
    y.push_back(yy);
  }

  // Sparse 2D array                                                                                    
  vector<int> D[40000];
  for (int i = 0; i < N; i++) D[y[i]].push_back(x[i]);
  for (int i = 0; i < H; i++) {
    sort(D[i].begin(), D[i].end());
    D[i].erase(unique(D[i].begin(), D[i].end()), D[i].end());
  }

  int ans = 0;
  int cnt[40000] = { 0 }; // dead pixel column count of Q pixels                                        

  for (int y = 0; y < Q; y++) {
    for (int x = 0; x < D[y].size(); x++) {
      cnt[D[y][x]] += 1;
    }
  }
  for (int y = 0; y < (H - Q + 1); y++) {
    int l = 0;
    for (int x = 0; x < W + 1; x++) {        // an alternative to this x-axis sweep                     
      if (x == W || cnt[x] > 0) {            // would be: foreach dead pixel, calculate                 
        ans += max(0, (x - l) - P + 1);      // how many possible positions there are in the            
        l = x + 1;                           // gap from dead pixel to l.                               
      }
    }
    if (y < H - Q) { // shift column count down y-axis                                                  
      for (int e = 0; e < D[  y  ].size(); e++) cnt[D[  y  ][e]] -= 1;
      for (int e = 0; e < D[y + Q].size(); e++) cnt[D[y + Q][e]] += 1;
    }
  }
  *r = ans;
}

int main() {
  int n; cin >> n;
  vector<thread> threads;
  int ans[100];
  for (int i = 0; i < n; i++) {
    threads.push_back(thread(solve, &ans[i]));
  }
  for (int i = 0; i < n; i++) {
    threads[i].join();
  }
  for (int t = 0; t < n; t++) {
    cout << "Case #" << (t+1) << ": " << ans[t] << endl;
  }
  return 0;
}