Instantly share code, notes, and snippets.

What would you like to do?
#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);
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;
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);
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);
// 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;
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));
while(lit!=leaves.end()) {
const PII& p = *lit;
if (PX(p)!=x) break;
cremove(PX(p), PY(p));
if (x!=ww) {
// printf("X=%d, curi=%d\n", x, curi);
ans += curi;
printf("Case #%d: %d\n", caseNum, ans);
int main() {
int caseCount;
REP(i, 1, caseCount+1)
return 0;
void unittest() {
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment