Petrozavodsk 2012 day 6 I

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

#define f first
#define s second
#define mp make_pair
#define pb push_back
#define forit(it,con) for (typeof(con.begin()) it = con.begin(); it != con.end(); ++it)
#define f0(a) memset(a, 0, sizeof(a))
#define all(v) v.begin(), v.end()
#define pii pair<int,int>
#define ll long long

#ifdef WIN32
    #define I64 "%I64d"
#else
    #define I64 "%lld"
#endif
const int maxn = 200000;

const int inf = (int)1e9 * 2;

struct Tree {
    Tree *L, *R;
    int val;
    Tree(int _val = inf) {
        L = R = 0;
        val = _val;
    }

    Tree(Tree *l, Tree *r) {
        L = l; R = r;
        val = inf;
        if (L) val = min(val, L -> val);
        if (R) val = min(val, R -> val);
    }
} *root;
int n;

pii a[maxn];
pii A[4][maxn];
int Y[4][maxn];
int Yn[4];
Tree *ver[4][maxn];


inline Tree * Build( int l, int r) {
    if (l > r) return 0;
    if (l == r) return new Tree();
    int mid = (l + r) >> 1;
    return new Tree(Build(l, mid), Build(mid + 1, r));
}

inline Tree * update(Tree *v, int pos, int val, int l, int r) {
    if (l > r) return 0;
    if (l == r) return new Tree(min(val, v->val));

    int mid = (l + r) >> 1;

    if (pos <= mid)
        return new Tree(update(v->L, pos, val, l, mid), v->R);
    else
        return  new Tree(v->L, update(v->R, pos, val, mid + 1, r));

}

inline void Create(int cur) {

    for (int i = 0; i < n; ++i) {
        A[cur][i] = a[i];
        Y[cur][Yn[cur]++] = a[i].s;
    }


    sort(Y[cur], Y[cur] + Yn[cur]);
    Yn[cur] = unique(Y[cur], Y[cur] + Yn[cur]) - Y[cur];

    sort(A[cur], A[cur] + n);

    root = Build(1, Yn[cur]);
    cerr << clock() / (double)CLOCKS_PER_SEC << " running kirdi " << endl;

    for (int i = n - 1; i >= 0; --i) {
        int pos = lower_bound(Y[cur], Y[cur] + Yn[cur], A[cur][i].s) - Y[cur] + 1;
        root = update(root, pos, A[cur][i].f + A[cur][i].s, 1, Yn[cur]);
        ver[cur][i] = root;
    }
    cerr << clock() / (double)CLOCKS_PER_SEC << " running wykty " << endl;


}

inline int findMin(Tree *v, int l, int r, int sl, int sr) {
    if (l > r || sl > sr)  return inf;
    if (min(sr, r) - max(sl, l) < 0) return inf;

    if (l <= sl && sr <= r) return v -> val;

    int mid = (sl + sr) >> 1;

    return min(findMin(v -> L, l, r, sl, mid), findMin(v -> R, l, r, mid + 1, sr));
}

inline int Dist(int cur, int x, int y) {
    int px = lower_bound(A[cur], A[cur] + n, mp(x, -inf)) - A[cur];

    int py = lower_bound(Y[cur], Y[cur] + Yn[cur], y) - Y[cur];

    if (px == n || py == Yn[cur]) return inf;

    return findMin(ver[cur][px], py + 1, Yn[cur], 1, Yn[cur]) - x - y;
}

int main() {
    #ifdef LOCAL
        freopen("in","r",stdin);
        freopen("out","w",stdout);
    #endif
    int A, B, C, D, E, F, M, q;
    scanf("%d%d", &n, &q);
    scanf("%d", &M);
    scanf("%d%d%d", &A, &B, &C);
    scanf("%d%d%d", &D, &E, &F);

    for (int i = 0; i < n; ++i) {
        int x, y;
        scanf("%d%d", &x, &y);
        a[i] = mp(x - y, x + y);
    }


    for (int i = 0; i < 2; ++i) {

        for (int j = 0; j < 2; ++j) {
            Create(i * 2 + j);

            for (int k = 0; k < n; ++k)
                a[k].s *= -1;
        }

        for (int k = 0; k < n; ++k)
            a[k].f *= -1;

    }

    int x, y;
    scanf("%d%d", &x, &y);
    long long anssum = 0;
    for (int i = 0; i < q; ++i) {

        int nx = x - y, ny = x + y;

        int ans = Dist(0, nx, ny);
        ans = min(ans, Dist(1, nx, -ny));
        ans = min(ans, Dist(2, -nx, ny));
        ans = min(ans, Dist(3, -nx, -ny));
        ans >>= 1;

        x = (abs(1ll * A * x + 1ll * B * ans + C) % (2 * M + 1)) - M;
        y = (abs(1ll * D * y + 1ll * E * ans + F) % (2 * M + 1)) - M;
        anssum += ans;
    }
    cout << anssum << endl;
    return 0;
}