Cod sursa(job #1110834)

Utilizator PatrikStepan Patrik Patrik Data 18 februarie 2014 13:43:52
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
    #include<cstdio>
    #include<vector>
    #include<algorithm>
    using namespace std;
    #define PII pair<int,int>
    #define mp make_pair
    #define pb push_back
    vector<PII> v,u;
    int N , M , n , X , Y , sol;

    void read();
    int abs(int k)
    {
        if(k < 0)return -k;
        return k;
    }
    int up(PII k, vector<PII> v);
    int down(PII k, vector<PII> v);
    void solve();
    void write();

    int main()
    {
        read();
        solve();
        write();
        return 0;
    }

    void read()
    {
        int x , y;
        freopen("zc.in" , "r" , stdin );
        scanf("%d%d" , &N , &M );
        for(int i = 1 ; i <= N ; ++i )
        {
            scanf("%d%d\n" , &x , &y );
            for(int k = -2 ; k <= 2 ; ++k )
                for(int p = -2 ; p <= 2 ; ++p )
                    if(abs(k)+abs(p) <= 2)
                        v.pb(mp(x+k,y+p));
        }
    }

    void solve()
    {
        char c;
        int d , p1 , p2;
        sort(v.begin(),v.end());
        v.resize(unique(v.begin() , v.end()) - v.begin());
        n = 0;
        for(int i = 1 ; i < (int)v.size() ; ++i )
            if(v[i] != v[i-1])
                v[++n] = v[i];
        v.resize(n+1);
        for(int i = 0 ; i < (int)v.size() ; ++i )
            u.pb(mp(v[i].second , v[i].first));
        sort(u.begin(),u.end());
        for(int i = 1 ; i <= M ; ++i )
        {
            scanf("%c%d\n" , &c , &d );
            if(c == 'N')
            {
                p1 = up(mp(X,Y+d),v);
                p2 = down(mp(X,Y+1),v);
                sol+=p1-p2-1;
                Y+=d;
            }
            if(c == 'S')
            {
                p1 = up(mp(X,Y-1),v);
                p2 = down(mp(X,Y-d),v);
                sol+=p1-p2-1;
                Y-=d;
            }
            if(c == 'E')
            {
                p1 = up(mp(Y,X+d),u);
                p2 = down(mp(Y,X+1),u);
                sol+=p1-p2-1;
                X+=d;
            }
            if(c =='V')
            {
                p1 = up(mp(Y,X-1),u);
                p2 = down(mp(Y,X-d),u);
                sol+=p1-p2-1;
                X-=d;
            }
        }
    }

    int up(PII k , vector<PII> a)
    {
        if(k >= a[n])return n+1;
        if(k < a[0])return 0;
        int st = 0 , dr = n , m;
        while(st < dr)
        {
            m = (st+dr)/2;
            if(a[m] <= k)st = m+1;
            else dr = m;
        }
        return dr;
    }

    int down( PII k , vector<PII> a)
    {
        if(k > a[n])return n;
        if(k <= a[0])return -1;
        int st = -1 , dr = n+1 , m;
        while(st < dr)
        {
            m = (st+dr+1)/2;
            if(a[m] >= k)dr = m-1;
            else st = m;
        }
        return st;
    }

    void write()
    {
        freopen("zc.out" , "w" , stdout );
        printf("%d" , sol);
   }