Cod sursa(job #1074516)

Utilizator tudorv96Tudor Varan tudorv96 Data 7 ianuarie 2014 18:36:29
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;

ifstream fin ("zc.in");
ofstream fout ("zc.out");

const int N = 14e5 + 5;

pair <int, int> vx[N], vy[N];
int n, m, x, y, k, kx;
long long sol;

int abs(int x) {
    return (x > -x ? x : -x);
}

int last_query(pair<int, int> v[N], pair <int, int> P) {
    int poz = -1;
    for (int step = (1 << 17); step; step >>=1)
        if (poz + step < k && v[poz + step] <= P)
            poz += step;
    return poz;
}

int first_query(pair <int, int> v[N], pair <int, int> P) {
    if (P > v[k-1])
        return k;
    int poz = -1;
    for (int step = (1 << 17); step; step >>= 1)
        if (poz + step < k && v[poz + step] < P)
            poz += step;
    return poz;
}

int main() {
    fin >> n >> m;
    while (n--) {
        int x, y;
        fin >> x >> y;
        for (int i = -2; i <= 2; ++i)
            for (int j = -2; j <= 2; ++j)
                if (abs(i) + abs(j) <= 2 && (x+i || y+j))
                    vx[kx++] = make_pair (x+i, y+j);
    }
    sort (vx, vx + kx);
    for (int i = 0; i < kx; ++i)
        if (!i || vx[i] != vx[i-1])
            vx[k++] = vx[i];
    for (int i = 0; i < k; ++i)
        vy[i] = make_pair (vx[i].second, vx[i].first);
    sort (vy, vy + k);
    while (m--) {
        char d; int dist;
        fin >> d >> dist;
        if (d == 'S') {
            sol += last_query(vx, make_pair(x, y)) - first_query(vx, make_pair (x, y - dist));
            y -= dist;
        }
        if (d == 'N') {
            sol += last_query(vx, make_pair(x, y + dist)) - first_query(vx, make_pair (x, y));
            y += dist;
        }
        if (d == 'V') {
            sol += last_query(vy, make_pair(y, x)) - first_query(vy, make_pair(y, x - dist));
            x -= dist;
        }
        if (d == 'E') {
            sol += last_query(vy, make_pair(y, x + dist)) - first_query(vy, make_pair(y, x));
            x +=dist;
        }
        int poz = last_query(vx, make_pair (x, y));
        if (vx[poz] == make_pair (x, y) && m)
            sol--;
    }
    fout << sol;
}