Cod sursa(job #2122837)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 5 februarie 2018 15:59:03
Problema Ograzi Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 kb
#include <fstream>
#include <algorithm>

using namespace std;

ofstream fout ("ograzi.out");

class InputReader {
	public:
        InputReader() {}
        InputReader(const char *name) {
            fin = fopen(name, "r");
			buffpos = Size - 1;
        }
        inline InputReader &operator >>(int &n) {
			char ch = nextpos();
            while(ch < '0' || ch > '9') {
                ch = nextpos();
            }

            n = 0;
            while('0' <= ch && ch <= '9') {
                n = n * 10 + ch - '0';
                ch = nextpos();
            }
            return *this;
        }
    private:
        FILE *fin;
        static const int Size = 1 << 17;
        int buffpos;
        char buff[Size];

        inline char nextpos() {
            ++ buffpos;
            if(buffpos == Size) {
                buffpos = 0;
                fread(buff, Size, 1, fin);
            }
			return buff[ buffpos ];
        }
} fin ("ograzi.in");

const int nmax = 1e5 + 5;
const int mmax = 5e4;

int n, m, cnt, n2;

struct pct {
    int x, y;

    inline bool operator < (const pct &shp) const {
        return x < shp.x;
    }
} v[nmax + 1], q[mmax + 1];
int aux[nmax + 1], valy[nmax + 1];
int aib[nmax + 1];

inline int lsb (int x) {
    return x & -x;
}

void update (int pos, int val) {
    for (int i = pos; i <= cnt; i += lsb( i ))
        aib[ i ] += val;
}

int query (int pos) {
    int sum = 0;
    for (int i = pos; i > 0; i -= lsb( i ))
        sum += aib[ i ];
    return sum;
}

void normalizare_oi () {
    for (int i = 1; i <= n; ++ i)
        aux[ i ] = v[ i ].y;

    sort(aux + 1, aux + n + 1);
    cnt = 0;
    for (int i = 1; i <= n; ) {
        int j = i;
        valy[ ++ cnt ] = aux[ i ];

        while (j <= n && aux[ i ] == aux[ j ])
            ++ j;
        i = j;
    }

    for (n2 = 1; (n2 << 1) <= cnt; n2 <<= 1) {
    }
}

int bs (int val) {
    int ans = cnt + 1;
    for (int step = n2; step > 0; step >>= 1) {
        if (ans - step > 0 && valy[ans - step] >= val)
            ans -= step;
    }
    return ans;
}

int main () {
    int dx, dy;
    fin >> m >> n >> dx >> dy;

    for (int i = 1; i <= m; ++ i) {
        int x, y;
        fin >> x >> y;

        q[ i ].x = x, q[ i ].y = y;
    }

    for (int i = 1; i <= n; ++ i) {
        fin >> v[ i ].x >> v[ i ].y;
    }
    normalizare_oi();

    for (int i = 1; i <= n; ++ i) {
        v[ i ].y = bs(v[ i ].y);
    }

    sort(v + 1, v + n + 1);
    sort(q + 1, q + m + 1);

    int bagate = 1, scoase = 1;
    int ans = 0;

    for (int i = 1; i <= n; ++ i) {
        while (bagate <= m && q[ bagate ].x <= v[ i ].x) {
            int x = bs(q[ bagate ].y);
            update(x, 1);

            x = bs(q[ bagate ].y + dy + 1);
            update(x, -1);

            ++ bagate;
        }
        while (scoase <= m && q[ scoase ].x + dx + 1 <= v[ i ].x) {
            int x = bs(q[ scoase ].y);
            update(x, -1);

            x = bs(q[ scoase ].y + dy + 1);
            update(x, 1);

            ++ scoase;
        }

        if (query(v[ i ].y)) {
            ++ ans;
        }

    }

    fout << ans << "\n";

    fout.close();
    return 0;
}