Cod sursa(job #1920254)

Utilizator ionanghelinaIonut Anghelina ionanghelina Data 9 martie 2017 23:12:42
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<bits/stdc++.h>
using namespace std;
pair<int,int> v[130005];
int dv,n,m,x,y,px,py,sol;
vector<pair<int,int> > vx,vy;
char c;
int it1,it2;
void Add(int x,int y)
{
    v[++dv]={x,y};
    v[++dv]={x+1,y};
    v[++dv]={x+2,y};
    v[++dv]={x-1,y};
    v[++dv]={x-2,y};
    v[++dv]={x,y+1};
    v[++dv]={x,y+2};
    v[++dv]={x,y-1};
    v[++dv]={x,y-2};
    v[++dv]={x+1,y+1};
    v[++dv]={x+1,y-1};
    v[++dv]={x-1,y+1};
    v[++dv]={x-1,y-1};
}
int main()
{
    freopen("zc.in","r",stdin);
    freopen("zc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        Add(x,y);
    }
    sort(v+1,v+dv+1);
    for(int i=1;i<=dv;i++)
    {
        if((i==1 || !(v[i].first==v[i-1].first && v[i].second==v[i-1].second)) && !(!v[i].first && !v[i].second))
        {
            vx.push_back(v[i]);
            vy.push_back({v[i].second,v[i].first});
        }
    }
    sort(vx.begin(),vx.end());
    sort(vy.begin(),vy.end());
    vx.push_back({INT_MAX,INT_MAX});
    vy.push_back({INT_MAX,INT_MAX});
    px=0;
    py=0;
    for(int i=1;i<=m;i++)
    {
        scanf("\n");
        scanf("%c",&c);
        scanf("%d",&x);
        pair<int,int> pi=make_pair(px,py);
        pair<int,int> pf;
        if(c=='N')
        {
            pf.first=pi.first-x;
            pf.second=pi.second;
            px-=x;
            pair<int,int> pf1,pi1;
            pf1.second=pf.first;
            pf1.first=pf.second;
            pi1.second=pi.first;
            pi1.first=pi.second;
            it1=upper_bound(vy.begin(),vy.end(),pi1)-1-vy.begin();
            it2=lower_bound(vy.begin(),vy.end(),pf1)-vy.begin();
            sol=sol+(it1-it2+1);

        }
            else
        if(c=='S')
        {
            px+=x;
            pf.first=pi.first+x;
            pf.second=pi.second;
            pair<int,int> pf1,pi1;
            pf1.second=pf.first;
            pf1.first=pf.second;
            pi1.second=pi.first;
            pi1.first=pi.second;
            it1=upper_bound(vy.begin(),vy.end(),pf1)-1-vy.begin();
            it2=lower_bound(vy.begin(),vy.end(),pi1)-vy.begin();
            sol=sol+(it1-it2+1);
        }
            else
        if(c=='E')
        {
            py+=x;
            pf.first=pi.first;
            pf.second=pi.second+x;
            it1=upper_bound(vx.begin(),vx.end(),pf)-1-vx.begin();
            it2=lower_bound(vx.begin(),vx.end(),pi)-vx.begin();
            sol=sol+(it1-it2+1);
        }
            else
        if(c=='V')
        {
            py-=x;
            pf.first=pi.first;
            pf.second=pi.second-x;
            it1=upper_bound(vx.begin(),vx.end(),pi)-1-vx.begin();
            it2=lower_bound(vx.begin(),vx.end(),pf)-vx.begin();
            sol=sol+(it1-it2+1);
        }
    }
    printf("%d\n",sol);
    return 0;
}