Poj Solution 2445

http://poj.org/problem?id=2445

#include"stdio.h"
#include"algorithm"
using namespace std;
int l[1500][1500],r[1500][1500],u[1500][1500],d[1500][1500],lu[1500][1500],rd[1500][1500];
int n;
inline int max(int a,int b)
{
    return a>b?a:b;
}
inline int min(int a,int b)
{
    return a<b?a:b;
}
bool init()
{
    int i,j,m,k,a,b;
    char c;
    if(scanf("%d",&n)!=1)
        return 0;
    scanf("%d",&m);
    for(i=0;i<n;i++)
    for(j=0;j<n;j++)
        r[i][j]=d[i][j]=0;
    while(m--)
    {
        getchar();
        scanf("%c%d%d%d",&c,&i,&j,&k);
        i--,j--;
        if(c=='H')
        {
            r[i][j]=max(r[i][j],k);
        }
        else
        {
            d[i][j]=max(d[i][j],k);
        }
    }    
    for(i=0;i<n;i++)
    {
        a=0,b=0;
        for(j=0;j<n;j++)
        {
            if(j>b)b=r[i][j]+j,a=j;
            else if(r[i][j]+j>b)b=r[i][j]+j;
            l[i][j]=a;
        }
        a=n-1,b=n-1;
        for(j=n-1;j>=0;j--)
        {
            if(j<b)b=l[i][j],a=j;
            else if(l[i][j]<b)b=l[i][j];
            r[i][j]=a;
        }
    }
    for(j=0;j<n;j++)
    {
        a=0,b=0;
        for(i=0;i<n;i++)
        {
            if(i>b)b=d[i][j]+i,a=i;
            else if(d[i][j]+i>b)b=d[i][j]+i;
            u[i][j]=a;
        }
        a=n-1,b=n-1;
        for(i=n-1;i>=0;i--)
        {
            if(i<b)b=u[i][j],a=i;
            else if(u[i][j]<b)b=u[i][j];
            d[i][j]=a;
        }
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            lu[i][j]=min(j-l[i][j],i-u[i][j]);
            rd[i][j]=min(r[i][j]-j,d[i][j]-i);
        }
    }

    return 1;
}
int m,c[1500],id[1500],x[1500],y[1500];
inline int lowbit(int x)
{
    return x&(x^(x-1));
}

bool cmp(int a,int b)
{
    return rd[x[a]][y[a]]+a<rd[x[b]][y[b]]+b;
}
int count(int bx,int by)
{
    int i,j,k,ans=0;
    m=min(n-bx,n-by);
    for(i=0;i<m;i++)
        id[i]=i,x[i]=bx+i,y[i]=by+i,c[i]=0;    
    sort(id,id+m,cmp);    
    for(i=0,j=0;i<m;i++)
    {
        k=i+1;
        while(k)
        {
            ans+=c[k];
            k-=lowbit(k);
        }        
        k=i-lu[bx+i][by+i]/*-1+1*/;
        while(k)
        {
            ans-=c[k];
            k-=lowbit(k);
        }        
        k=i+1;
        while(k<=m)
        {
            c[k]++;
            k+=lowbit(k);
        }
        while(j<m&&(id[j]+rd[x[id[j]]][y[id[j]]])<=i)
        {
            k=id[j++]+1;
            while(k<=m)
            {
                c[k]--;
                k+=lowbit(k);
            }
        }
    }

    return ans;
}
void doit()
{
    int x,y,ans=0;
    for(x=0;x<n;x++)
        ans+=count(x,0);
    for(y=1;y<n;y++)
        ans+=count(0,y);
    printf("%dn",ans);
}
int main()
{
    while(init())
    {
        doit();
    }
    return 0;
}