Cod sursa(job #1491789)

Utilizator felixiPuscasu Felix felixi Data 26 septembrie 2015 09:59:05
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define x first
#define y second
#define mp(a, b) make_pair(a, b)
#define pb(v, a) v.push_back(a)
#define sz(a) a.size()

vector< pair<int, int> > v, u;
int m;
long long rez;

void readdata()
{
    freopen("zc.in", "r", stdin);
    freopen("zc.out", "w", stdout);

    int nr, i, j, pas, a, b, lim, cont = 1, n1 = 0, n2 = 0;

    scanf("%d %d", &nr, &m);
    for (pas = 0; pas < nr; ++pas)
    {
        scanf("%d %d", &a, &b);
        for (i = a-2; i <= a+2; ++i)
        for (j = b-2; j <= b+2; ++j)
            if (abs(i-a) + abs(j-b) <= 2)
            if (i != 0 || j != 0)
            {
                pb(v, mp(i, j));
                pb(u, mp(j, i));
            }
    }
    sort(u.begin(), u.end());
    sort(v.begin(), v.end());
    lim = sz(v);
    if (lim == 0) return;
    for (i = 1; i < lim; ++i)
    {
        if (v[i] != v[i-1]) v[++n1] = v[i];
        if (u[i] != u[i-1])
        {
            u[++n2] = u[i];
            cont++;
        }
    }
    cont = sz(v)-cont;
    for (i = 0; i < cont; ++i)
    {
        v.pop_back();
        u.pop_back();
    }
}

int search1(pair<int, int> k)
{
    int st = 0, dr = sz(v)-1, m;

    while (st < dr)
    {
        m = (st+dr+1)/2;
        if (v[m] <= k) st = m;
        else dr = m-1;
    }
    if (dr < st) return -1;
    if (st == 0 && v[st] > k) return -1;
    return st;
}

int search2(pair<int, int> k)
{
    int st = 0, dr = sz(u)-1, m;

    while (st < dr)
    {
        m = (st+dr+1)/2;
        if (u[m] <= k) st = m;
        else dr = m-1;
    }
    if (dr < st) return -1;
    if (st == 0 && u[st] > k) return -1;
    return st;
}

void solve()
{
    int X = 0, Y = 0, pas, d, p1, p2, i;
    char ch;

    for (pas = 0; pas < m; ++pas)
    {
        scanf(" %c %d", &ch, &d);
        if (ch == 'N')
        {
            p1 = search1(mp(X, Y+d));
            p2 = search1(mp(X, Y));
            rez += p1-p2;
            Y += d;
        }
        if (ch == 'S')
        {
            p1 = search1(mp(X, Y-d-1));
            p2 = search1(mp(X, Y-1));
            rez += p2-p1;
            Y -= d;
        }
        if (ch == 'E')
        {
            p1 = search2(mp(Y, X+d));
            p2 = search2(mp(Y, X));
            rez += p1 - p2;
            X += d;
        }
        if (ch == 'V')
        {
            p1 = search2(mp(Y, X-d-1));
            p2 = search2(mp(Y, X-1));
            rez += p2 - p1;
            X -= d;
        }
    }
}

void writedata()
{
    printf("%Ld\n", rez);
}

int main()
{
    readdata();
    solve();
    writedata();
    return 0;
}