AOJ 2426 Treasure Hunt

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426

{n} 個の点と {m} 個の長方形が与えられる。各長方形の辺上または内部にある点の数を求めよ。

解法

座標圧縮・累積和の前計算といった工夫をしないとTLEする。

template<typename T>
inline void compless(vector<T> & c){
    sort(all(c));
    c.erase(unique(all(c)),c.end());
}
template<typename T>
inline size_t idx(T i, vector<T> const& c){
    return lower_bound(all(c),i) - c.begin();
}
 
int n,m;
int xs[5000], ys[5000];
int sum[5100][5100]={};
 
int main(){
    scanf("%d%d",&n,&m);
    vector<int> x(n),y(n);
    rep(i,n){
        scanf("%d%d",xs+i,ys+i);
        x[i]=xs[i];
        y[i]=ys[i];
    }
    compless(x);
    compless(y);
    rep(i,n){
        int fx=idx(xs[i],x);
        int fy=idx(ys[i],y);
        sum[fy+1][fx+1]++;
    }
    rep(i,y.size())rep(j,x.size()){
        sum[i+1][j+1]+=sum[i+1][j]+sum[i][j+1]-sum[i][j];
    }
 
    rep(i,m){
        int lx,ly,rx,ry;
        scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
        lx = idx(lx,x);
        rx = idx(rx+1,x);
        ly = idx(ly,y);
        ry = idx(ry+1,y);
        printf("%d\n",sum[ry][rx]-sum[ry][lx]-sum[ly][rx]+sum[ly][lx]);
    }
}