Cod sursa(job #1746361)

Utilizator ionut98Bejenariu Ionut Daniel ionut98 Data 23 august 2016 07:54:39
Problema Zota & Chidil Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream f("zc.in");
ofstream g("zc.out");
const int dx[]={0,0,0,0,0,-1,-1,-1,-2,1,1,1,2};
const int dy[]={-2,-1,0,1,2,-1,0,1,0,-1,0,1,0};
int ka,kb;
pair<int,int>A[1300005],B[1300005];
int cautare(pair<int,int>P,pair<int,int>v[])
{
    int lo=1,hi=kb,mid;
    if(v[kb]<=P)
      return kb+1;
    while(lo<hi)
    {
        mid=(lo+hi)>>1;
        if(v[mid]>P)
          hi=mid;
        else
          lo=mid+1;
    }
    return lo;
}
int main()
{
    int n,m,a,b,L,x,y,ans;
    char D;
    f>>n>>m;
    for(int i=1;i<=n;i++)
    {
        f>>a>>b;
        for(int j=0;j<13;j++)
          if(a+dx[j]||b+dy[j])
            A[++ka]=make_pair(a+dx[j],b+dy[j]);
    }
    sort(A+1,A+ka+1);
    for(int i=1;i<=ka;i++)
      if(A[i]!=make_pair(B[kb].second,B[kb].first))
      {
          A[++kb]=A[i];
          B[kb].first=A[kb].second;
          B[kb].second=A[kb].first;
      }
    sort(B+1,B+kb+1);
    x=y=ans=0;
    for(int i=1;i<=m;i++)
    {
        f>>D>>L;
        if(D=='E')
        {
            ans+=cautare(make_pair(y,x+L),B)-cautare(make_pair(y,x),B);
            x+=L;
        }
        if(D=='V')
        {
            ans+=cautare(make_pair(y,x-1),B)-cautare(make_pair(y,x-L-1),B);
            x-=L;
        }
        if(D=='N')
        {
            ans+=cautare(make_pair(x,y+L),A)-cautare(make_pair(x,y),A);
            y+=L;
        }
        if(D=='S')
        {
            ans+=cautare(make_pair(x,y-1),A)-cautare(make_pair(x,y-L-1),A);
            y-=L;
        }
    }
    g<<ans;
    return 0;
}