Cod sursa(job #1886495)

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

using namespace std;

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

typedef long long i64;

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

int n, m, k;

struct str {
    int x, y;
} v1[nmax*afectat+1], v2[nmax*afectat+1], aux[nmax*afectat+1];

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;

    return sol;
}

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

bool cmp( str x, str y ) {
    if ( x.x==y.x ) {
        return x.y<y.y;
    }
    return x.x<y.x;
}

int f( str v[], str x ) {
    if ( v[k].x<x.x || (v[k].x==x.x && v[k].y<=x.y) ) {
        return k;
    }

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

    return ans;
}

int main(  ) {
    fin>>n>>m;
    for ( int i= 1, x, y; i<=n; ++i ) {
        fin>>x>>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, cmp );
    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, cmp );

    i64 sol= 0;
    for ( int cnt= 1, x= 0, y= 0; cnt<=m; ++cnt ) {
        string a;
        int b;
        fin>>a>>b;
        if ( a[0]=='N' ) {
            sol= sol+f(v1, mp(x, y+b))-f(v1, mp(x, y));
            y+= b;
        } else if ( a[0]=='S' ) {
            sol= sol+f(v1, mp(x, y-1))-f(v1, mp(x, y-b-1));
            y-= b;
        } else if ( a[0]=='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;
}