Cod sursa(job #3234028)

Utilizator Dia3141Costea Diana Stefania Dia3141 Data 5 iunie 2024 23:34:17
Problema Zota & Chidil Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <fstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream cin("zc.in");
ofstream cout("zc.out");
int n,m,ex,ey,nx,ny,sx,sy,x,y,dx[]={0,-1,0,1,-2,-1,0,1,2,-1,0,1,0},dy[]={2,1,1,1,0,0,0,0,0,-1,-1,-1,-2};
pair<int,int>vx[1300005],vy[1300005];
char d;
void unice(pair<int,int> v[],int& n){
    int nr=1;
    for(int i=2;i<=n;i++)
        if(v[nr].first!=v[i].first||v[nr].second!=v[i].second)
            v[++nr]=v[i];
    n=nr;
}
int up(int a,int b,pair<int,int> v[],int n){
    int p=0,st=1,dr=n;
    while(st<=dr){
        int mid=(st+dr)/2;
        if(v[mid].first==a){
            if(v[mid].second>=b)
                dr=mid-1,p=mid;
            else
                st=mid+1;
        }else if(v[mid].first<a)
            st=mid+1;
        else
            dr=mid-1;
    }
    return p;
}
int low(int a,int b,pair<int,int> v[],int n){
    int p=0,st=1,dr=n;
    while(st<=dr){
        int mid=(st+dr)/2;
        if(v[mid].first==a){
            if(v[mid].second<=b)
                st=mid+1,p=mid;
            else
                dr=mid-1;
        }else if(v[mid].first<a)
            st=mid+1;
        else
            dr=mid-1;
    }
    return p;
}
long long sol;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x>>y;
        for(int k=0;k<13;k++)
            if(x+dx[k]!=0||y+dy[k]!=0){
                vx[++nx]=make_pair(x+dx[k],y+dy[k]);
                vy[++ny]=make_pair(y+dy[k],x+dx[k]);
            }
    }
    sort(vx+1,vx+nx+1);
    sort(vy+1,vy+ny+1);
    unice(vx,nx);
    unice(vy,ny);
    for(int i=1;i<=m;i++){
        cin>>d>>x;
        if(d=='S'){
            int a=up(sx,min(sy-1,sy-x),vx,nx),b=low(sx,max(sy-1,sy-x),vx,nx);
            if(a!=0&&b!=0)
                sol+=b-a+1;
            sy-=x;
        }else if(d=='N'){
            int a=up(sx,min(sy+x,sy+1),vx,nx),b=low(sx,max(sy+x,sy+1),vx,nx);
            if(a!=0&&b!=0)
                sol+=b-a+1;
            sy+=x;
        }else if(d=='E'){
            int a=up(sy,min(sx+1,sx+x),vy,ny),b=low(sy,max(sx+1,sx+x),vy,ny);
            if(a!=0&&b!=0)
                sol+=b-a+1;
            sx+=x;
        }else{
            int a=up(sy,min(sx-x,sx-1),vy,ny),b=low(sy,max(sx-x,sx-1),vy,ny);
            if(a!=0&&b!=0)
                sol+=b-a+1;
            sx-=x;
        }
    }
    cout<<sol;
    return 0;
}