読者です 読者をやめる 読者になる 読者になる

JOI 2010 春合宿 day1-2 「Sengoku」

JOI

なかなかにめんどくさい。

#include<cstdio>
#include <cstdlib>
#include<queue>
#include<set>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main(){
	int l, n, inx, iny, z, c, j;
	ll ans = 0;
	set<int> sx, sy;
	set<int>::iterator it;
	priority_queue<int, vector<int>, greater<int> > x[2];
	priority_queue<int> y[2];
	
	scanf("%d%d",&l,&n);
	
	rep(i,n){
		scanf("%d%d",&inx,&iny);
		sx.insert(inx+iny);
		sy.insert(inx-iny);
	}
	
	for(it = sx.begin(); it != sx.end(); it++){z = l-abs(*it - l + 1); x[z % 2].push(z); ans += z;}
	for(it = sy.begin(); it != sy.end(); it++){z = l-abs(*it); y[z % 2].push(z); ans += z;}
	
	
	rep(i,2){
		c = 0; j = (i+l+1) % 2;
		while(!x[i].empty()){
			while(!y[j].empty() && y[j].top() >= l+1-x[i].top()){y[j].pop(); c++;}
			ans -= c;
			x[i].pop();
		}
	}
	
	printf("%lld\n",ans);
	return 0;
}