Cod sursa(job #883478)

Utilizator maritimCristian Lambru maritim Data 20 februarie 2013 02:20:57
Problema Zota & Chidil Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<fstream>
#include<assert.h>
using namespace std;
 
ifstream f("zc.in");
ofstream g("zc.out");
 
#define MaxN 100100
#define mp make_pair
#define mij ((li+ls)>>1)
#define ll long long
#define MaxDoi (13*MaxN)
#define MaxS (24*MaxN)
 
int N,M,I,Sol;
int Doi[MaxDoi];
vector<pair<int,int> > A,B,C;
char S[MaxS];
 
inline int abs(int a)
{
    return a < 0 ? -a : a;
}
 
inline void addTraps(int a,int b)
{
    for(int i=-2;i<=2;i++)
        if(a || b+i)
            C.push_back(mp(a,b+i));
 
    for(int i=-1;i<=1;i++)
    {
        if(a-1 || b+i)
            C.push_back(mp(a-1,b+i));
        if(a+1 || b+i)
            C.push_back(mp(a+1,b+i));
    }
     
    if(a-2 || b)
        C.push_back(mp(a-2,b));
    if(a+2 || b)
        C.push_back(mp(a+2,b));
}
 
inline int getInt(void)
{
    int semn = 1,a = 0;
 
    for(;S[I] != '-' && !isdigit(S[I]);++I);
    if(S[I] == '-') semn = -1, I++;
    for(;isdigit(S[I]);a = a*10+S[I++]-'0');
     
    return semn*a;
}
 
void citire(void)
{
    int a,b;
 
    f.getline(S,MaxS,EOF);
    N = getInt();
    M = getInt();
    for(int n=1;n<=N;++n)
    {
        b = getInt();
        a = getInt();
 
        addTraps(a,b);
    }
}
 
void creareTraps(void)
{
    sort(C.begin(),C.end());
  
    A.push_back(C[0]);
    B.push_back(mp(C[0].second,C[0].first));
 
    for(int i=1;i<C.size();i++)
        if(C[i] != C[i-1])
            A.push_back(C[i]),
            B.push_back(mp(C[i].second,C[i].first));
 
    sort(B.begin(),B.end());
}

void preprocesareDoi(void)
{
    Doi[0] = 1;
    
    for(int i=1;i<MaxDoi;i++)
        if(i == Doi[i-1]<<1)
            Doi[i] = i;
        else
            Doi[i] = Doi[i-1];
}
 
inline int cautBinx(int li,int ls,int a,int k)
{
    int doi = Doi[ls-li+1],p = ls,x;

    for(;doi;doi >>= 1)
        if(p-doi >= 0 )
        {
            x = (!k) ? B[p-doi].first : A[p-doi].first;

            if(x >= a)
                p -= doi;
        }

    return p;
}

inline int cautBiny(int li,int ls,int a,int k)
{
    if(li > ls)
        return li;
 
    int x = (!k) ? B[mij].second : A[mij].second;
 
    if(x >= a)
        return cautBiny(li,mij-1,a,k);
    return cautBiny(mij+1,ls,a,k);
}
 
void Rezolvare(void)
{
    char op;
    int x,y,a,b,x1,x2,y1,y2,dx,dy;
 
    x = y = 0;
 
    creareTraps();
    preprocesareDoi();
 
    for(int i=1;i<=M;i++)
    {
        for(;!isalpha(S[I]);++I);
        op = S[I++];
        b = getInt();
 
        a = (op == 'E' || op == 'V');
 
        switch(op)
        {
            case 'N' : dx = b, dy = 0;
                break;
            case 'E' : dy = b, dx = 0;
                break;
            case 'S' : dx = -b, dy = 0;
                break;
            default : dy = -b, dx = 0;
        }
 
        if(a)
        {
            x1 = cautBinx(0,A.size()-1,x,a);
            x2 = cautBinx(0,A.size()-1,x+1,a);
 
            y1 = cautBiny(x1,x2-1,y+1,a);
            y2 = cautBiny(x1,x2-1,y+dy,a);
        }
        else
        {
            x1 = cautBinx(0,A.size()-1,y,a);
            x2 = cautBinx(0,A.size()-1,y+1,a);
 
            y1 = cautBiny(x1,x2-1,x+1,a);
            y2 = cautBiny(x1,x2-1,x+dx,a);
        }
 
        x += dx;
        y += dy;
 
        Sol += abs(y2-y1);
    }
}
 
int main()
{
    citire();
    Rezolvare();
 
    g << Sol << "\n";
}