Cod sursa(job #1886509)

Utilizator Athena99Anghel Anca Athena99 Data 20 februarie 2017 22:24:10
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include <algorithm>
#include <fstream>
#include <string>

#define x first
#define y second
#define mp make_pair

using namespace std;

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

typedef long long i64;
typedef pair <int, int> str;

const int nmax= 100000;
const int afectat= 13;

int n, m, k;
str v1[nmax*afectat+1], v2[nmax*afectat+1], aux[nmax*afectat+1];

inline int av( int x ) {
    if ( x<0 ) {
        x= -x;
    }
    return x;
}

int f( str v[], str x ) {
    if ( v[k]<x ) {
        return k;
    }

    int ans= 0;
    for ( int i= k-1; ans<i; ) {
        int aux= (ans+i)/2;
        if ( v[aux+1]<x ) {
            ans= aux+1;
        } else {
            i= aux;
        }
    }

    return ans;
}

string buffer;
string::iterator buffer_it;

void read_int( int &x ) {
    for ( ; (*buffer_it>'9' || *buffer_it<'0') && *buffer_it!='-'; ++buffer_it ) ;

    int sign= 1;
    if ( *buffer_it=='-' ) {
        sign= -1;
        ++buffer_it;
    }
    for ( x= 0; *buffer_it>='0' && *buffer_it<='9'; ++buffer_it ) {
        x= x*10+*buffer_it-'0';
    }
    x*= sign;
}

void read_letter( char &x ) {
    for ( ; *buffer_it<'A' || *buffer_it>'Z'; ++buffer_it ) ;
    x= *buffer_it;
    ++buffer_it;
}

int main(  ) {
    getline( fin, buffer, (char)0 );
    buffer_it= buffer.begin();

    read_int(n), read_int(m);
    for ( int i= 1, x, y; i<=n; ++i ) {
        read_int(x), read_int(y);
        for ( int a= x-2; a<=x+2; ++a ) {
            for ( int b= y-2+av(x-a); b<=y+2-av(x-a); ++b ) {
                if ( a!=0 || b!=0 ) {
                    aux[++k]= mp(a, b);
                }
            }
        }
    }

    sort( aux+1, aux+k+1 );
    int k2= 0;
    for ( int i= 1; i<=k; ++i ) {
        if ( aux[i].x!=v1[k2].x || aux[i].y!=v1[k2].y ) {
            v1[++k2]= aux[i];
            v2[k2].x= aux[i].y, v2[k2].y= aux[i].x;
        }
    }
    k= k2;
    sort( v2+1, v2+k+1 );

    i64 sol= 0;
    for ( int cnt= 1, x= 0, y= 0; cnt<=m; ++cnt ) {
        char a;
        int b;
        read_letter(a), read_int(b);
        if ( a=='N' ) {
            sol= sol+f(v1, mp(x, y+b))-f(v1, mp(x, y));
            y+= b;
        } else if ( a=='S' ) {
            sol= sol+f(v1, mp(x, y-1))-f(v1, mp(x, y-b-1));
            y-= b;
        } else if ( a=='E' ) {
            sol= sol+f(v2, mp(y, x+b))-f(v2, mp(y, x));
            x+= b;
        } else {
            sol= sol+f(v2, mp(y, x-1))-f(v2, mp(y, x-1-b));
            x-= b;
        }
    }

    fout<<sol<<"\n";

    return 0;
}