IOI '07 Pairs

2    75971    poao899    49440K    4656MS    G++     3.16K     2010-04-26 08:47:55                        .



Inspired by warehouse?

不過三維作法很有趣，竟然有一個n維曼哈頓轉Chebyshev distance的作法，


可惜依現在硬體技術，作用有限

事實上這兩個都有優點，可惜自由轉換僅限於1或2維

算是個遺憾吧(?

//*****************************************

#include<algorithm>
#define N 100010
#define lb(x) ((x)&-(x))
struct ele{
    int i, j, k, w, x, y, z;
    void _2get();
    void _3get();
}_ar[N];
int ar[N], front, rear;
int b, n, d, m, nmax; long long ans;
int getint(){
    int g=0; char c=getchar();
    while(c==10||c==32||c==9)c=getchar();
    while(c>='0'&&c<='9'){
        g= g*10+c-48;
        c=getchar();
    }
    return g;
}
//case 2
#define _2LEN 75010
void ele::_2get(){
    i= getint(); j= getint();
    x= i+j; y= i-j;
}
bool _2cmp(ele a, ele b){
    return a.y<b.y;
}
int _2bit[_2LEN*3];
inline int _2qry(int a){
    if(a<0) return 0;
    int ret= 0;
    while(a>0){
        ret+= _2bit[a];
        a-= lb(a);
    }
    return ret;
}
inline int _2find(int l, int r){
    return _2qry(r)-_2qry(l-1);
}
inline void _2adj(int a, int r){
    while(a<=nmax){
        _2bit[a]+= r;
        a+= lb(a);
    }
}
//case 3
#define _3LEN 76
void ele::_3get(){
    i= getint(); j= getint(); k= getint();
    w= i-j-k; x= i+j-k+m; y= i-j+k+m; z= i+j+k;
}
bool _3cmp(ele a, ele b){
    return a.w<b.w;
}
int _3bit[_3LEN*3+1][_3LEN*3+1][_3LEN*3+1];
inline int _3qry(int x, int y, int z){
    int ret= 0;
    for(int xx=x; xx>0; xx-=lb(xx))
        for(int yy=y; yy>0; yy-=lb(yy))
            for(int zz=z; zz>0; zz-=lb(zz))
                ret+= _3bit[xx][yy][zz];
    return ret;
}
inline int _3find(int lx, int ly, int lz, int rx, int ry, int rz){
    if(rx> nmax)rx= nmax;
    if(ry> nmax)ry= nmax;
    if(rz> nmax)rz= nmax;
    int ret= _3qry(rx,ry,rz);
    ret= ret- _3qry(lx-1,ry,rz)- _3qry(rx,ly-1,rz)- _3qry(rx,ry,lz-1);
    ret= ret+ _3qry(rx,ly-1,lz-1)+ _3qry(lx-1,ry,lz-1)+ _3qry(lx-1,ly-1,rz);
    ret= ret- _3qry(lx-1,ly-1,lz-1);
    return ret;
}
inline void _3adj(int x, int y, int z, int r){
    for(int xx=x; xx<=nmax; xx+=lb(xx))
        for(int yy=y; yy<=nmax; yy+=lb(yy))
            for(int zz=z; zz<=nmax; zz+=lb(zz))
                _3bit[xx][yy][zz]+= r;
}
int main(){
    b= getint(); n= getint(); d= getint(); m= getint();
    //case 1
    if(b==1){
        for(int i=0; i<n; i++) ar[i]= getint();
        std::sort(ar, ar+n);
        for(front=rear=0; rear<n; rear++){
            while(ar[front]+d< ar[rear]) front++;
            ans+= rear-front;
        }
    }
    //case 2
    else if(b==2){
        nmax= _2LEN*3;
        for(int i=0; i<n; i++) _ar[i]._2get();
        std::sort(_ar, _ar+n, _2cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].y+d< _ar[rear].y){
                _2adj(_ar[front].x, -1);
                front++;
            }
            ans+= _2find(_ar[rear].x-d, _ar[rear].x+d);
            _2adj(_ar[rear].x, 1);
        }
    }
    //case 3
    else if(b==3){
        nmax= _3LEN*3;
        for(int i=0; i<n; i++) _ar[i]._3get();
        std::sort(_ar, _ar+n, _3cmp);
        for(front=rear=0; rear<n; rear++){
            while(_ar[front].w+d< _ar[rear].w){
                _3adj(_ar[front].x, _ar[front].y, _ar[front].z, -1);
                front++;
            }
            ans+= _3find(_ar[rear].x-d, _ar[rear].y-d, _ar[rear].z-d, _ar[rear].x+d, _ar[rear].y+d, _ar[rear].z+d);
            _3adj(_ar[rear].x, _ar[rear].y, _ar[rear].z, 1);
        }
    }
    printf("%I64d\n", ans);
}