Cod sursa(job #3172969)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 21 noiembrie 2023 17:32:53
Problema Zota & Chidil Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
int dx[]={0,1,-1,0,0,1,1,-1,-1,-2,2,0,0};
int dy[]={0,0,0,1,-1,1,-1,1,-1,0,0,2,-2};
int i,d,nrca,nrcb,n,m,l,c,x,nr,y;
long long sol;
char ch;
pair <int,int> a,b,pctx[1300001],pcty[1300001];
int cb (pair <int,int> x,pair <int,int> v[])
{
    int st=1,dr=nr,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}
int main ()
{
    fin>>n>>m;
    for (i=1; i<=n; i++)
    {
        fin>>x>>y;
        swap (x,y);
        for (d=0; d<=12; d++)
        {
            if (x+dx[d]==0&&y+dy[d]==0)
                continue;
            nr++;
            pctx[nr]=make_pair (x+dx[d],y+dy[d]);
            pcty[nr]=make_pair (y+dy[d],x+dx[d]);
        }
    }
    sort (pctx+1,pctx+nr+1);
    sort (pcty+1,pcty+nr+1);
    nrca=nrcb=1;
    for (i=2; i<=nr; i++)
    {
        if (pctx[i]!=pctx[nrca])
            pctx[++nrca]=pctx[i];
        if (pcty[i]!=pcty[nrcb])
            pcty[++nrcb]=pcty[i];
    }
    nr=nrca;
    l=c=0;
    for (i=1; i<=m; i++)
    {
        fin>>ch>>x;
        if (ch=='S')
        {
            a=make_pair (c,l-x-1);
            b=make_pair (c,l);
            sol+=cb (b,pcty)-cb (a,pcty);
            l-=x;
        }
        else
            if (ch=='N')
        {
            a=make_pair (c,l-1);
            b=make_pair (c,l+x);
            sol+=cb (b,pcty)-cb (a,pcty);
            l+=x;
        }
        else if (ch=='E')
        {
            a=make_pair (l,c-1);
            b=make_pair (l,c+x);
            sol+=cb (b,pctx)-cb (a,pctx);
            c+=x;
        }
        else
            if (ch=='V')
        {
            a=make_pair (l,c-x-1);
            b=make_pair (l,c);
            sol+=cb (b,pctx)-cb (a,pctx);
            c-=x;
        }
    }
    fout<<sol;
    return 0;
}