Cod sursa(job #2148713)

Utilizator uniculrobyrobertoManea Robert uniculrobyroberto Data 1 martie 2018 22:09:10
Problema Zota & Chidil Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("zc.in");
ofstream out("zc.out");
const int NMAX = 14*1e5;

vector< pair<int,int> > xprio,yprio,xfinal,yfinal;

int main()
{
    int n,m,rez=0,steps,x,y;
    char dir;
    in >> n >> m;
    for (int i = 1; i<=n; i++)
    {
        in >> x >> y;
        for (int j = -2; j<=2; j++)
            for (int k = -2; k<=2; k++)
                if ((x+j || y+k) && (abs(k)+abs(j)<=2))
                {
                    xprio.push_back({x+j,y+k});
                    yprio.push_back({y+k,x+j});
                }
    }
    sort(xprio.begin(),xprio.end());
    sort(yprio.begin(),yprio.end());
    for (int i = 0; i<xprio.size(); i++)
    {
        while (xprio[i] == xprio[i+1] && i<xprio.size()-1)
            i++;
        xfinal.push_back({xprio[i].first,xprio[i].second});
        yfinal.push_back({yprio[i].first,yprio[i].second});
    }
    sort(xfinal.begin(),xfinal.end());
    sort(yfinal.begin(),yfinal.end());
    x=0,y=0;
    for (int i = 1; i<=m; i++)
    {
        in >> dir >> steps;
        if (dir == 'N')
        {
            rez+=upper_bound(xfinal.begin(),xfinal.end(),make_pair(x,y+steps))-lower_bound(xfinal.begin(),xfinal.end(),make_pair(x,y+1));
            y+=steps;
        }
        else if (dir == 'S')
        {
            rez+=upper_bound(xfinal.begin(),xfinal.end(),make_pair(x,y-1))-lower_bound(xfinal.begin(),xfinal.end(),make_pair(x,y-steps));
            y-=steps;
        }
        else if (dir == 'E')
        {
            rez+=upper_bound(yfinal.begin(),yfinal.end(),make_pair(y,x+steps))-lower_bound(yfinal.begin(),yfinal.end(),make_pair(y,x+1));
            x+=steps;
        }
        else
        {
            rez+=upper_bound(yfinal.begin(),yfinal.end(),make_pair(x,y))-lower_bound(yfinal.begin(),yfinal.end(),make_pair(y,x-steps));
            x-=steps;
        }
    }
    out << rez;
}