Cod sursa(job #1838151)

Utilizator badea_adi1999Badea Adrian Catalin badea_adi1999 Data 31 decembrie 2016 02:07:12
Problema Zota & Chidil Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
ifstream f("zc.in");
ofstream g("zc.out");
set <pair<int,int> > vl,vc;
set <pair<int,int > > ::iterator it;
vector <pair<int,int> > l,c;
long long sol;
int n,m,w,x,y;
char p;

void put(int x,int y)
{
    if (x==0&&y==0)
        return;
    vl.insert(make_pair(x,y));
    vc.insert(make_pair(y,x));

}
void solve(vector <pair<int,int> > v,int a,int b1,int b2)
{
    int i,j,t;
    pair <int,int> p=make_pair(a,b1),q=make_pair(a,b2);

    for (j=0,i=1<<22;i;i>>=1)
        if (j+i<w&&v[j+i]<p)
            j+=i;
    if (v[j]<p)
        j++;
    if (j>=w)
        return;

    for (t=0,i=1<<22;i;i>>=1)
        if (t+i<w&&v[t+i]<=q)
            t+=i;

    if (v[t]<=q)
        sol+=t-j+1;
}
int main()
{
    int i,j,k;
    f>>n>>m;
    for (i=1;i<=n;i++) {
        f>>x>>y;f.get();
        put(x-2,y);
        for (j=y-1;j<=y+1;j++)
            put(x-1,j),put(x+1,j);
        for (j=y-2;j<=y+2;j++)
            put(x,j);
        put(x+2,y);
    }
    for (it=vl.begin();it!=vl.end();it++) {
        x=it->first;
        y=it->second;
        l.push_back(make_pair(x,y));
        w++;
    }
    for (it=vc.begin();it!=vc.end();it++) {
        x=it->first;
        y=it->second;
        c.push_back(make_pair(x,y));
    }
    x=0,y=0;
    for (i=1;i<=m;i++) {
        f.get(p);f>>j;f.get();
        if (p=='N')
            solve(l,x,y+1,y+j),y+=j;
        if (p=='S')
            solve(l,x,y-j,y-1),y-=j;
        if (p=='E')
            solve(c,y,x+1,x+j),x+=j;
        if (p=='V')
            solve(c,y,x-j,x-1),x-=j;
    }
    g<<sol<<'\n';
    return 0;
}