AOJ 2426 Treasure Hunt
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426
個の点と 個の長方形が与えられる。各長方形の辺上または内部にある点の数を求めよ。
解法
座標圧縮・累積和の前計算といった工夫をしないと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]); } }