Cod sursa(job #803684)

Utilizator Teodor94Teodor Plop Teodor94 Data 28 octombrie 2012 00:16:10
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.59 kb
#include <cstdio>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> point;

const int N = 1400000;
const int INF = 0x7fffffff;

int n, m, nr, xc, yc, nextx, nexty;
vector<point> v, p;

void make_points(int a, int b) {
    for (int i = a - 2; i <= a + 2; ++i)
        for (int j = b - 2; j <= b + 2; ++j)
            if ( (abs(i - a) + abs(j - b) <= 2) && (i != 0 || j != 0)) {
                v.push_back(make_pair(i, j));
                p.push_back(make_pair(j, i));
            }
}

void read() {
    v.push_back(make_pair(-INF, -INF));
    p.push_back(make_pair(-INF, -INF));

    scanf("%d%d\n", &n, &m);

    for (int i = 1; i <= n; ++i) {
        int a, b;
        scanf("%d%d\n", &a, &b);

        make_points(a, b);
    }
}

void duplicates() {
    sort(v.begin(), v.end());
    sort(p.begin(), p.end());

    int nr = v.size(), nrv = 0, nrp = 0;

    for (int i = 1; i < nr; ++i) {
        if (v[i] != v[i - 1])
            v[++nrv] = v[i];

        if (p[i] != p[i - 1])
            p[++nrp] = p[i];
    }

    for (int i = 1; i <= nr - nrp; ++i) {
        v.pop_back();
        p.pop_back();
    }
}

int binary_search_v(point q) {
    int i, pas = 1 << 21;

    for (i = 0; pas; pas >>= 1)
        if (i + pas <= nr && v[i + pas] <= q)
            i += pas;
    return i;
}

int binary_search_p(point q) {
    int i, pas = 1 << 21;

    for (i = 0; pas; pas >>= 1)
        if (i + pas <= nr && p[i + pas] <= q)
            i += pas;

    return i;
}

int search(char dir, int lg) {
    if (dir == 'N') {
        int left = binary_search_v(make_pair(xc, yc)), right = binary_search_v(make_pair(xc, yc + lg));

        yc += lg;

        return right - left;
    }

    if (dir == 'S') {
        int left = binary_search_v(make_pair(xc, yc - lg - 1)), right = binary_search_v(make_pair(xc, yc - 1));

        yc -= lg;

        return right - left;
    }

    if (dir == 'E') {
        int left = binary_search_p(make_pair(yc, xc)), right = binary_search_p(make_pair(yc, xc + lg));

        xc += lg;

        return right - left;
    }

    int left = binary_search_p(make_pair(yc, xc - lg - 1)), right = binary_search_p(make_pair(yc, xc - 1));

    xc -= lg;

    return right - left;
}

void solve() {
    nr = v.size();

    int total = 0;

    for (int i = 1; i <= m; ++i) {
        char dir;
        int lg;
        scanf("%c %d\n", &dir, &lg);

        total += search(dir, lg);
    }

    printf("%d\n", total);
}

int main() {
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);

    read();

    duplicates();

    solve();
    
    return 0;
}