Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI春合宿 2010-day1 sengoku

問題文 : 戦国時代

解法 :

見張り達の見張るエリアを, 左上と右上の線で分ける.

まずは左上側の線の処理を以下のように行う.

点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.

右側の点も, 点P(L - 1, y - (L - x - 1))に移し, 同様にどれだけの領地を見張っているかが分かる. ここで, 偶奇に注意して, 交点を引いてやれば O(N log N)時間ですべてのみはられるエリアを求めることが出来る.

コード :

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long lint;

inline int ct(int x, vector<int> &v)
{
	return ((upper_bound(v.begin(), v.end(), x) - v.begin() - 1) - (upper_bound(v.begin(), v.end(), -x - 1) - v.begin() - 1));
}

int main()
{
	int l, n;
	int x[100000], y[100000];
	
	scanf("%d %d", &l, &n);
	
	for (int i = 0; i < n; i++) scanf("%d %d", x + i, y + i);
	
	lint ret = 0;
	
	vector<int> vs;
	for (int i = 0; i < n; i++) vs.push_back(y[i] - x[i]);
	
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	
	vector<int> even, odd;
	for (int i = 0; i < vs.size(); i++) abs(vs[i]) & 1 ? (odd.push_back(vs[i])) : (even.push_back(vs[i]));
	
	for (vector<int>::iterator it = vs.begin(); it != vs.end(); it++){
		ret += min(l + *it, l - *it);
	}
	
	vs.clear();
	
	for (int i = 0; i < n; i++) vs.push_back(y[i] - (l - 1 - x[i]));
	sort(vs.begin(), vs.end());
	vs.erase(unique(vs.begin(), vs.end()), vs.end());
	
	for (vector<int>::iterator it = vs.begin(); it != vs.end(); it++){
		int p = l - 1 - abs(*it);
		ret += min(l + *it, l - *it) - ct(p, p & 1 ? odd : even);
	}
	
	printf("%lld\n", ret);
}