AOJ2426 Treasure Hunt

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

解法

使用可能メモリ量が200000[KB]と余裕があるので、
座標圧縮+包除原理で解きました。

以下のコードで0:59 sec 52328 KBでAC。
pressX、pressYをuniqueにしたほうがよかったかも知れません。

#include<stdio.h>
#include<limits.h>
#include<vector>
#include<algorithm>
using namespace std;

struct P{int x,y;P(int x,int y):x(x),y(y){}P(){}};

vector<int>pressX,pressY;

const int C=5120;
short treasure[C][C]={};

// 座標圧縮した結果を返す
// テーブルにない隙間の座標の場合、テーブルの小さい方の座標に寄せて返す
P Compress(int x,int y)
{
	return P( upper_bound(pressX.begin(),pressX.end(),x)-pressX.begin()-1,
		upper_bound(pressY.begin(),pressY.end(),y)-pressY.begin()-1);
}

int CountPoint(int x,int y)
{
	P p=Compress(x,y);
	return treasure[p.y][p.x];
}
int CountArea(int x1,int x2, int y1, int y2)
{
	int lu=CountPoint(x1-1,y1-1);
	int ru=CountPoint(x2,y1-1);
	int ld=CountPoint(x1-1,y2);
	int rd=CountPoint(x2,y2);
	//printf("x1:%d y1:%d x2:%d y2:%d    左上;%d 右上:%d 左下:%d 右下:%d\n",x1,y1,x2,y2,lu,ru,ld,rd);
	return rd+lu-ru-ld;
}
int main()
{
	int n,m,i,j,x[5000],y[5000];
	scanf("%d%d",&n,&m);
	pressX.reserve(n+2);
	pressY.reserve(n+2);
	for(i=0;i<n;++i)
	{
		scanf("%d%d",x+i,y+i);
		pressX.push_back(x[i]);
		pressY.push_back(y[i]);
	}
	pressX.push_back(INT_MAX);
	pressX.push_back(INT_MIN);
	pressY.push_back(INT_MAX);
	pressY.push_back(INT_MIN);
	sort(pressX.begin(),pressX.end());
	sort(pressY.begin(),pressY.end());


	// 包除原理用のテーブルの作成
	for(i=0; i<n; ++i)
	{
		P p=Compress(x[i],y[i]);
		++treasure[p.y][p.x];
	}
	for(i=1; i<C; ++i)
	{
		treasure[i][0]+=treasure[i-1][0];
		treasure[0][i]+=treasure[0][i-1];
	}
	for(i=1; i<C; ++i)
		for(j=1; j<C; ++j)
			treasure[i][j] += treasure[i][j-1]+treasure[i-1][j]-treasure[i-1][j-1];


	int x1,x2,y1,y2;
	while(m--)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		printf("%d\n",CountArea(x1,x2,y1,y2));
	}
	return 0;
}