Cod sursa(job #859253)

Utilizator stoicatheoFlirk Navok stoicatheo Data 19 ianuarie 2013 22:39:37
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 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;
}