tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 0618: Rampart

2011合宿のDragon原液1mlを1000倍に薄めて付属の計量カップ1杯とってきたくらい簡単。
これで本選5とは…(というか去年と一昨年が難しすぎるだけかも)

#include<stdio.h>
#include<set>
#include<algorithm>
#include<vector>
using namespace std;
bool t[4100][4100];
short ul[4100][4100];
short dl[4100][4100];
short ll[4100][4100];
short rl[4100][4100];
int bit[5000];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<5000;a|=a+1)bit[a]+=b;
}
pair<int,int>ev[5000];
int P;
long long count(vector<int>L,vector<int>R){
	int n=L.size();
	for(int i=0;i<5000;i++)bit[i]=0;
	for(int i=0;i<n;i++)ev[i]=make_pair(i-L[i],i);
	std::sort(ev,ev+n);
	long long ret=0;
	int at=0;
	for(int i=0;i<n;i++){
		while(at<n&&ev[at].first<i){
			add(ev[at].second,1);
			at++;
		}
		int left=i+P-1;
		int right=i+R[i]-1;
		if(left<=right)ret+=sum(left,right);
	}
	//printf("%lld ",ret);
	return ret;
}
int main(){
	int H,W,L;
	scanf("%d%d%d%d",&H,&W,&P,&L);
	bool hanten=false;
	if(H>W){
		swap(H,W);
		hanten=true;
	}
	for(int i=0;i<L;i++){
		int p,q;
		scanf("%d%d",&p,&q);
		p--;q--;
		if(hanten)swap(p,q);
		t[p][q]=1;
	}
	for(int i=0;i<H;i++)for(int j=0;j<W;j++){
		if(t[i][j]){
			ul[i][j]=ll[i][j]=0;
		}else{
			if(i==0)ul[i][j]=1;
			else ul[i][j]=ul[i-1][j]+1;
			if(j==0)ll[i][j]=1;
			else ll[i][j]=ll[i][j-1]+1;
		}
	}
	for(int i=H-1;i>=0;i--)for(int j=W-1;j>=0;j--){
		if(t[i][j]){
			dl[i][j]=rl[i][j]=0;
		}else{
			if(i==H-1)dl[i][j]=1;
			else dl[i][j]=dl[i+1][j]+1;
			if(j==W-1)rl[i][j]=1;
			else rl[i][j]=rl[i][j+1]+1;
		}
	}
	for(int i=0;i<H;i++)for(int j=0;j<W;j++){
		rl[i][j]=min(rl[i][j],dl[i][j]);
		ll[i][j]=min(ll[i][j],ul[i][j]);
	}
	long long ret=0;
	for(int i=1;i<H;i++){
		vector<int>tl(i);
		vector<int>tr(i);
		for(int j=0;j<i;j++){
			tl[j]=ll[H-i+j][j];
			tr[j]=rl[H-i+j][j];
		}
		ret+=count(tl,tr);
	}
	for(int i=1;i<H;i++){
		vector<int>tl(i);
		vector<int>tr(i);
		for(int j=0;j<i;j++){
			tl[j]=ll[j][W-i+j];
			tr[j]=rl[j][W-i+j];
		}
		ret+=count(tl,tr);
	}
	for(int i=0;i<=W-H;i++){
		vector<int>tl(H);
		vector<int>tr(H);
		for(int j=0;j<H;j++){
			tl[j]=ll[j][i+j];
			tr[j]=rl[j][i+j];
		}
		ret+=count(tl,tr);
	}
	printf("%lld\n",ret);
}