博客

多么伤心啊

考场上只想出暴力


一看题解才发现这么简单


人傻没办法

还有。。

uoj上T是什么鬼啊

常数怎么这么大？！

强开O2还多T了一个点！？

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
#define youhua __attribute__((optimize("O2")))
char c;
youhua
inline void read(int &a){a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}
youhua inline int min(int a,int b){return a<b?a:b;}
youhua inline int max(int a,int b){return a>b?a:b;}
int n,m;
youhua 
inline int Pl(int x,int y){return (x-1)*m+y;}


struct S
{
    int u,len;

youhua inline friend bool operator <(S a,S b){return a.len<b.len;}
}; 

struct Heap
{
    int con;
    S D[1000001],swp;
youhua inline void clear(){con=0;}
youhua inline S top(){return D[1];} 
int per,now,lc,rc,f;

youhua inline void pop()
    {
       D[1]=D[con--],now=1;
       while(now<=con)
       {
        lc=now<<1;rc=lc|1;
        if(rc<=con)
        {
          per=D[lc]<D[rc]?lc:rc;
          if(D[per]<D[now]){swp=D[now],D[now]=D[per],D[per]=swp;}
          else break;
          now=per;
       }    else if(lc<=con&&D[lc]<D[now]){swp=D[now],D[now]=D[lc],D[lc]=swp,now=lc;break;}

        else break; 
       }
    }


youhua     inline void push(S New)
    {
        D[now=++con]=New;
        while(1^now)
        {
            f=now>>1;
            if(D[now]<D[f]){swp=D[now],D[now]=D[f],D[f]=swp;}
            else break;
            now=f;
        }
    }

youhua bool empty(){
    return con==0;
    }
}Di;

struct Chain
{
    int u,len;
    Chain*next;
}*Head[100001];


youhua inline void Add(int u,int v,int len)
{
    Chain *tp=new Chain;
    tp->len=len;
    tp->next=Head[u];
    tp->u=v;
    Head[u]=tp;
}

youhua 
inline int X(int Nu){return (Nu-1)/m+1;}

youhua inline int Y(int Nu){return Nu%m?Nu%m:m;}
const
   int INF=1<<29;
int Dis[100001];

youhua inline void Dij(int start,int lx,int rx,int ly,int ry)
{

    int u;
    Di.clear();
    Di.push((S){start,0});
    for(int i=lx;i<=rx;i++)
      for(int j=ly;j<=ry;j++)
         Dis[Pl(i,j)]=INF;
    Dis[start]=0;
    while(!Di.empty())
    {
        u=Di.top().u;
        if(Dis[u]<Di.top().len){goto ed;}
        for(Chain *tp=Head[u];tp;tp=tp->next)
         {
          int x=X(tp->u),y=Y(tp->u);
          if(x<lx||x>rx||y<ly||y>ry)
           continue;
          if(Dis[u]+tp->len<Dis[tp->u])  
             {
                Dis[tp->u]=Dis[u]+tp->len;
                Di.push((S){tp->u,Dis[tp->u]});
             }
        }
        ed:
        Di.pop(); ;
   }
}

struct Query
{
    int x1,x2,y1,y2;
    int ans,d;

youhua inline friend bool operator <(Query a,Query b){return a.d<b.d;}
};
Query Sum[100001];
Query Cache[100001];
int t;
Query Cache2[100001];

youhua void Div(int lx,int rx,int ly,int ry,int ql,int qr)
{
    if(qr<ql)
      return;
    int i,midx,midy,Res,Ss,Con1,Con2;
    if(rx-lx>ry-ly)
      {
        midx=lx+rx>>1;
         for(i=ly;i<=ry;i++)      
            {
                Dij(Pl(midx,i),lx,rx,ly,ry);
                for(int j=ql;j<=qr;j++)
                   Sum[j].ans=min(Sum[j].ans,Dis[Pl(Sum[j].x1,Sum[j].y1)]+Dis[Pl(Sum[j].x2,Sum[j].y2)]);
            }
         Res=ql-1;
         Con1=0,Con2=0;
         for(i=ql;i<=qr;i++)
            if(max(Sum[i].x1,Sum[i].x2)<=midx)
                   Cache[++Con1]=Sum[i];
            else if(min(Sum[i].x1,Sum[i].x2)>midx)
                         Cache2[++Con2]=Sum[i];
            else Sum[++Res]=Sum[i];
         Ss=Res;
         for(i=1;i<=Con1;i++)
            Sum[++Ss]=Cache[i];
         for(i=1;i<=Con2;i++)
            Sum[++Ss]=Cache2[i]; 
         if(lx^rx)
              Div(lx,midx,ly,ry,Res+1,Res+Con1),Div(1+midx,rx,ly,ry,Res+Con1+1,qr);
      }
    else
      {

         midy=ly+ry>>1;
         for(i=lx;i<=rx;i++)      
            {
                Dij(Pl(i,midy),lx,rx,ly,ry);
                for(int j=ql;j<=qr;j++)
                   Sum[j].ans=min(Sum[j].ans,Dis[Pl(Sum[j].x1,Sum[j].y1)]+Dis[Pl(Sum[j].x2,Sum[j].y2)]);
             }
         Res=ql-1;
         Con1=0,Con2=0;
         for(i=ql;i<=qr;i++)
            if(max(Sum[i].y1,Sum[i].y2)<=midy)
                   Cache[++Con1]=Sum[i];
            else if(min(Sum[i].y1,Sum[i].y2)>midy)
                         Cache2[++Con2]=Sum[i];
            else Sum[++Res]=Sum[i];
         Ss=Res;
         for(i=1;i<=Con1;i++)
            Sum[++Ss]=Cache[i];
         for(i=1;i<=Con2;i++)
            Sum[++Ss]=Cache2[i]; 
         if(ly^ry)
              Div(lx,rx,ly,midy,Res+1,Res+Con1),Div(lx,rx,midy+1,ry,Res+Con1+1,qr); 
      }
}




youhua 
int main()
{
       int len;
       read(n),read(m);
       for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
          {
            read(len);
            Add(Pl(i,j),Pl(i,j+1),len);
            Add(Pl(i,j+1),Pl(i,j),len);
          }
        for(int i=1;i<n;i++)
         for(int j=1;j<=m;j++)
          {
            read(len);
            Add(Pl(i,j),Pl(i+1,j),len);
            Add(Pl(i+1,j),Pl(i,j),len);
          }
    int Q;
    read(Q);
    for(int i=1;i<=Q;i++)
       read(Sum[i].x1),
       read(Sum[i].y1),
       read(Sum[i].x2),
       read(Sum[i].y2),Sum[i].d=i,Sum[i].ans=INF;
    Div(1,n,1,m,1,Q);
    sort(Sum+1,Sum+1+Q);
    for(int i=1;i<=Q;i++)
     printf("%d\n",Sum[i].ans);
    return  0;
}