Cod sursa(job #1679346)

Utilizator akaprosAna Kapros akapros Data 7 aprilie 2016 21:49:36
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.03 kb
#include <bits/stdc++.h>
#define maxN 13 * 100002
#define ll long long
#define pii pair < int, int >
#define x first
#define y second
using namespace std;
pii pos;
int n, m, N;
ll ans;
pii v[maxN], V[maxN];
int bs(pii v[maxN], int cx, int cy)
{
    pii c;
    c.x = cx;
    c.y = cy;
    if(v[n] <= c)
        return n + 1;
    int i = 0, p = 1 << 20;
    while (p)
    {
        if (i + p <= n && v[i + p] <= c)
            i += p;
        p /= 2;
    }
    return i + 1;
}
/*void BRUT()
{
    int i, px, py;
    for (i = 1; i <= n; ++ i)
    {
        int cx, cy;
        scanf("%d %d", &cx, &cy);
        cx += 2000; cy += 2000;
        for (px = 0; px <= 2; ++ px)
            for (py = 0; py <= 2; ++ py)
                if (px + py <= 2)
                {
                    a[cx + px][cy + py] = 1;
                    a[cx - px][cy + py] = 1;
                    a[cx + px][cy - py] = 1;
                    a[cx - px][cy - py] = 1;
                }
    }
    coord pos;
    pos.x = pos.y = 2000;
    for (i = 1; i <= m; ++ i)
    {
        int x, j;
        char d;
        scanf("\n%c %d", &d, &x);
        if (d == 'N')
        {
            for (j = pos.y + 1; j <= pos.y + x; ++ j)
                ans += a[pos.x][j];
            pos.y += x;
        }
        if (d == 'S')
        {
            for (j = pos.y - 1; j >= pos.y - x; -- j)
                ans += a[pos.x][j];
            pos.y -= x;
        }
        if (d == 'E')
        {
            for (j = pos.x + 1; j <= pos.x + x; ++ j)
                ans += a[j][pos.y];
            pos.x += x;
        }
        if (d == 'V')
        {
            for (j = pos.x - 1; j >= pos.x - x; -- j)
                ans += a[j][pos.y];
            pos.x -= x;
        }
    }
    //printf("%lld", ans);
}*/
void read()
{
    int i, px, py;
    freopen("zc.in", "r", stdin);
    scanf("%d %d", &n, &m);
    N = 0;
    for (i = 1; i <= n; ++ i)
    {
        int cx, cy;
        scanf("%d %d", &cx, &cy);
        for (px = 0; px <= 2; ++ px)
            for (py = 0; py <= 2; ++ py)
                if (px + py <= 2)
                {
                    v[++ N].x = cx + px;
                    v[N].y = cy + py;
                    if (px)
                    {
                        v[++ N].x = cx - px;
                        v[N].y = cy + py;
                    }
                    if (py)
                    {
                        v[++ N].x = cx + px;
                        v[N].y = cy - py;
                    }
                    if (px && py)
                    {
                        v[++ N].x = cx - px;
                        v[N].y = cy - py;
                    }
                }
    }
}
void det_pos()
{
    int i;
    v[0].x = v[1].x + 1;
    sort(v + 1, v + N + 1);
    n = 0;
    for (i = 1; i <= N; ++ i)
        if (i == 1 || v[i].x != v[i - 1].x || v[i].y != v[i - 1].y)
        {
            v[++ n] = v[i];
            V[n].x = v[i].y;
            V[n].y = v[i].x;
        }
    sort(V + 1, V + n + 1);
}
void solve()
{
    int p, i;
    det_pos();
    //pii pos;
    pos.x = pos.y = 0;
    for (i = 1; i <= m; ++ i)
    {
        char d;
        int x, a, b;
        scanf("\n%c %d", &d, &x);

        if (d == 'N')
        {
            a = bs(v, pos.x, pos.y);
            pos.y += x;
            b = bs(v, pos.x, pos.y);
        }
        if (d == 'S')
        {
           b = bs(v, pos.x, pos.y - 1);
        pos.y -= x;
            a = bs(v, pos.x, pos.y - 1);
        }
        if (d == 'E')
        {
            a = bs(V, pos.y, pos.x);
            pos.x += x;
            b = bs(V, pos.y, pos.x);
        }
        if (d == 'V')
        {
             b = bs(V, pos.y, pos.x - 1);
            pos.x -= x;
            a = bs(V, pos.y, pos.x - 1);
        }
        ans += b - a;
    }
}
void write()
{
    freopen("zc.out", "w", stdout);
    printf("%lld", ans);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}