Cod sursa(job #2334440)
Utilizator | Data | 2 februarie 2019 17:04:17 | |
---|---|---|---|
Problema | Zota & Chidil | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 6.44 kb |
#include <fstream>
#include <algorithm>
using namespace std;
ifstream cin ("zc.in");
ofstream cout ("zc.out");
struct ura{
int x,y;
};
ura vc[1300005];
ura vl[1300005];
bool cmp1(ura a , ura b)
{
if (a.x<b.x)
return true;
else
if (a.x>b.x)
return false;
else
{
if (a.y<b.y)
return true;
return false;
}
}
bool cmp2(ura a , ura b)
{
if (a.y<b.y)
return true;
else
if (a.y>b.y)
return false;
else
{
if (a.x<b.x)
return true;
return false;
}
}
int main()
{
int n,mm,st,dr,x,y,s=0,m,cnt=0,i,j,l,c,cnt1=0,cnt2=0,lf,cf,dir;
char car;
cin>>n>>mm;
for (i=1;i<=n;i++)
{
cin>>c>>l;
vc[++cnt].x=l-2;
vc[cnt].y=c;
vc[++cnt].x=l-1;
vc[cnt].y=c-1;
vc[++cnt].x=l-1;
vc[cnt].y=c;
vc[++cnt].x=l-1;
vc[cnt].y=c+1;
vc[++cnt].x=l;
vc[cnt].y=c-2;
vc[++cnt].x=l;
vc[cnt].y=c-1;
vc[++cnt].x=l;
vc[cnt].y=c;
vc[++cnt].x=l;
vc[cnt].y=c+1;
vc[++cnt].x=l;
vc[cnt].y=c+2;
vc[++cnt].x=l+1;
vc[cnt].y=c-1;
vc[++cnt].x=l+1;
vc[cnt].y=c;
vc[++cnt].x=l+1;
vc[cnt].y=c+1;
vc[++cnt].x=l+2;
vc[cnt].y=c;
}
for (i=1;i<=cnt;i++)
{
vl[i].x=vc[i].x;
vl[i].y=vc[i].y;
}
cnt1=cnt2=cnt;
sort (vc+1,vc+cnt1+1,cmp2);
sort (vl+1,vl+cnt2+1,cmp1);
// for (i=1;i<=cnt;i++)
// cout<<vl[i].x<<" "<<vl[i].y<<endl;
// cout<<endl;
//for (i=1;i<=cnt;i++)
// cout<<vc[i].x<<" "<<vc[i].y<<endl;
l=0;
c=0;
lf=0;
cf=0;
for (i=1;i<=mm;i++)
{
cin>>car>>dir;
lf=l;
cf=c;
x=y=0;
if (car=='N')
{
lf+=dir;
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>c)
dr=m-1;
else
if (vc[m].y<c)
st=m+1;
else
{
if (vc[m].x<l)
st=m+1;
else
{
x=m;
dr=m-1;
}
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>c)
dr=m-1;
else
if (vc[m].y<c)
st=m+1;
else
{
if (vc[m].x>lf)
dr=m-1;
else
{
y=m;
st=m+1;
}
}
}
}
if (car=='E')
{
cf+=dir;
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>l)
dr=m-1;
else
if (vl[m].x<l)
st=m+1;
else
{
if (vl[m].y<c)
st=m+1;
else
{
x=m;
dr=m-1;
}
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>l)
dr=m-1;
else
if (vl[m].x<l)
st=m+1;
else
{
if (vl[m].y>cf)
dr=m-1;
else
{
y=m;
st=m+1;
}
}
}
}
if (car=='S')
{
lf-=dir;
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>c)
dr=m-1;
else
if (vc[m].y<c)
st=m+1;
else
{
if (vc[m].x<lf)
st=m+1;
else
{
x=m;
dr=m-1;
}
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].y>c)
dr=m-1;
else
if (vc[m].y<c)
st=m+1;
else
{
if (vc[m].x>l)
dr=m-1;
else
{
y=m;
st=m+1;
}
}
}
}
if (car=='V')
{
cf-=dir;
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vl[m].x>l)
dr=m-1;
else
if (vl[m].x<l)
st=m+1;
else
{
if (vl[m].y<cf)
st=m+1;
else
{
x=m;
dr=m-1;
}
}
}
st=1;
dr=cnt;
while (st<=dr)
{
m=(st+dr)/2;
if (vc[m].x>l)
dr=m-1;
else
if (vc[m].x<l)
st=m+1;
else
{
if (vc[m].y>c)
dr=m-1;
else
{
y=m;
st=m+1;
}
}
}
}
l=lf;
c=cf;
if (x<=y&&x!=0&&y!=0)
s+=(y-x+1);
}
cout<<s;
return 0;
}