Cod sursa(job #998383)

Utilizator poptibiPop Tiberiu poptibi Data 16 septembrie 2013 20:59:49
Problema Zota & Chidil Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.86 kb
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;

const int NMAX = 1300010;
const int DX[12] = {-2, -1, -1, -1, 0, 0, 0, 0, 1, 1, 1, 2};
const int DY[12] = {0, -1, 0, 1, -2, -1, 1, 2, -1, 0, 1, 0};

int N, M, X, Y, Steps, K;
pair<int, int> OX[NMAX], OY[NMAX];
char Dir;

int Find(pair<int, int> V[NMAX], int X, int Y)
{
    int Left = 1, Right = K, Mid;
    pair<int, int> Target = make_pair(X, Y);
    if(V[K] <= Target) return K + 1;

    while(Left <= Right)
    {
        Mid = (Left + Right) / 2;
        if(V[Mid] <= Target) Left = Mid + 1;
        else Right = Mid - 1;
    }
    return Left;
}

const int MaxB = 100000;
char Buf[MaxB];
int Ptr = 0;

int GetInt()
{
    int Ans = 0;
    while(!isdigit(Buf[Ptr]))
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isdigit(Buf[Ptr]))
    {
        Ans = Ans * 10 + Buf[Ptr] - '0';
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Ans;
}

char GetChar()
{
    char Ans;
    while(!isupper(Buf[Ptr]))
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    while(isupper(Buf[Ptr]))
    {
        Ans = Buf[Ptr];
        if(++ Ptr >= MaxB)
            fread(Buf, 1, MaxB, stdin), Ptr = 0;
    }
    return Ans;
}

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

    N = GetInt();
    M = GetInt();

    for(int i = 1; i <= N; ++ i)
    {
        X = GetInt();
        Y = GetInt();
        if(X != 0 || Y != 0) OX[++ K] = make_pair(X, Y);
        for(int j = 0; j < 12; ++ j)
            if(X + DX[j] != 0 || Y + DY[j] != 0)
                OX[++ K] = make_pair(X + DX[j], Y + DY[j]);
    }

    sort(OX + 1, OX + K + 1);
    OX[0].first = OX[1].first - 1;

    int KK = 0;
    for(int i = 1; i <= K; ++ i)
        if(OX[i] != OX[i - 1])
        {
            OX[++ KK] = OX[i];
            OY[KK] = make_pair(OX[KK].second, OX[KK].first);
        }

    K = KK;

    sort(OY + 1, OY + K + 1);

    int X = 0, Y = 0, Ans = 0;

    for(; M; M --)
    {
        Dir = GetChar();
        Steps = GetInt();
        int L, R;

        if(Dir == 'N')
        {
            L = Find(OX, X, Y);
            Y += Steps;
            R = Find(OX, X, Y);
        }else if(Dir == 'S')
        {
            R = Find(OX, X, Y - 1);
            Y -= Steps;
            L = Find(OX, X, Y - 1);
        }else if(Dir == 'V')
        {
            R = Find(OY, Y, X - 1);
            X -= Steps;
            L = Find(OY, Y, X - 1);
        }else
        {
            L = Find(OY, Y, X);
            X += Steps;
            R = Find(OY, Y, X);
        }

        Ans += R - L;
    }
    printf("%i\n", Ans);

    return 0;
}