JOI 春合宿 2013-day2 Construction

問題文 : 建設事業

解法 :
つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.

点のソートをするときに, x 座標またはy 座標が一緒だったときについて考慮していなくて5 日間暗い悩んでましたw
バグ, 気づくと自明だけどハマると泥沼になるのなんとかならんかなあ.

コード :

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define MAX_N (200010)
#define MAX_M (200010)
#define getpos(x, v) (lower_bound(x.begin(), x.end(), v) - x.begin())

using namespace std;

typedef long long lint;

vector<int> xs, ys;
int P[MAX_M], Q[MAX_M], R[MAX_M], S[MAX_M];

struct Point {
	int x, y, id;
	int xcnt, ycnt;
};

bool cmpx(const Point &a, const Point &b)
{
	if (a.x != b.x) return (a.x < b.x);
	return (a.y < b.y);
}

bool cmpy(const Point &a, const Point &b)
{
	if (a.y != b.y) return (a.y < b.y);
	return (a.x < b.x);
}

struct Line {
	int pos, p1, p2;
	Line(int pos, int p1, int p2) : pos(pos), p1(p1), p2(p2){};
};

bool operator < (const Line &a, const Line &b)
{
	return (a.pos < b.pos);
}

vector<Line> lX, lY;
vector<Point> pt;

int bit[MAX_N + 2 * MAX_M + 1];

void add(int k, int x)
{
	k++;
	while (k <= MAX_N + 2 * MAX_M){
		bit[k] += x; k += k & -k;
	}
}

int sum(int k)
{
	int ret = 0;
	k++;
	while (k){
		ret += bit[k]; k &= (k - 1);
	}
	return (ret);
}

struct Edge {
	int u, v, cost;
	Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
};

vector<Edge> es;

bool operator < (const Edge &a, const Edge &b)
{
	return (a.cost < b.cost);
}

int par[MAX_N];

void init()
{
	for (int i = 0; i < MAX_N; i++) par[i] = i;
}

int find(int x)
{
	if (x == par[x]) return (x);
	return (par[x] = find(par[x]));
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x == y) return;
	
	if (rand() & 1) par[y] = x;
	else par[x] = y;
}

bool same(int x, int y)
{
	return (find(x) == find(y));
}

int main()
{
	int N, M, C;
	
	scanf("%d %d %d", &N, &M, &C);
	
	pt.resize(N);
	for (int i = 0; i < N; i++){
		scanf("%d %d", &pt[i].x, &pt[i].y);
		pt[i].id = i;
		xs.push_back(pt[i].x); ys.push_back(pt[i].y);
	}
	
	for (int i = 0; i < M; i++){
		scanf("%d %d %d %d", P + i, Q + i, R + i, S + i);
		xs.push_back(P[i]); xs.push_back(R[i]);
		ys.push_back(Q[i]); ys.push_back(S[i]);
		lX.push_back(Line(Q[i], P[i], R[i])); lX.push_back(Line(S[i], P[i], R[i]));
		lY.push_back(Line(P[i], Q[i], S[i])); lY.push_back(Line(R[i], Q[i], S[i]));
	}
	
	sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());
	sort(ys.begin(), ys.end()); ys.erase(unique(ys.begin(), ys.end()), ys.end());
	
	int ptr = 0;
	sort(pt.begin(), pt.end(), cmpy);
	
	sort(lX.begin(), lX.end());
	for (int i = 0; i < lX.size(); i++){
		while (ptr != N && pt[ptr].y < lX[i].pos){
			pt[ptr].ycnt = sum(getpos(xs, pt[ptr].x)); ptr++;
		}
		add(getpos(xs, lX[i].p1), 1); add(getpos(xs, lX[i].p2) + 1, -1);
	}
	while (ptr != N){
		pt[ptr].ycnt = sum(getpos(xs, pt[ptr].x)); ptr++;
	}
	
	memset(bit, 0, sizeof(bit));
	ptr = 0;
	sort(pt.begin(), pt.end(), cmpx);
	
	sort(lY.begin(), lY.end());
	for (int i = 0; i < lY.size(); i++){
		while (ptr != N && pt[ptr].x < lY[i].pos){
			pt[ptr].xcnt = sum(getpos(ys, pt[ptr].y)); ptr++;
		}
		add(getpos(ys, lY[i].p1), 1); add(getpos(ys, lY[i].p2) + 1, -1);
	}
	while (ptr != N){
		pt[ptr].xcnt = sum(getpos(ys, pt[ptr].y)); ptr++;
	}
	
	sort(pt.begin(), pt.end(), cmpx);
	for (int i = 0; i < N - 1; i++){
		if (pt[i].x == pt[i + 1].x && pt[i].ycnt == pt[i + 1].ycnt){
			es.push_back(Edge(pt[i].id, pt[i + 1].id, abs(pt[i + 1].y - pt[i].y)));
		}
	}
	sort(pt.begin(), pt.end(), cmpy);
	for (int i = 0; i < N - 1; i++){
		if (pt[i].y == pt[i + 1].y && pt[i].xcnt == pt[i + 1].xcnt){
			es.push_back(Edge(pt[i].id, pt[i + 1].id, abs(pt[i + 1].x - pt[i].x)));
		}
	}
	
	sort(es.begin(), es.end());
	init();
	
	vector<lint> e;
	lint sumEdge[MAX_N];
	for (int i = 1; i < MAX_N; i++) sumEdge[i] = 1ll << 50;
	sumEdge[0] = 0;
	for (int i = 0; i < es.size(); i++){
		if (!same(es[i].u, es[i].v)){
			merge(es[i].u, es[i].v);
			sumEdge[e.size() + 1] = (lint)es[i].cost + sumEdge[e.size()];
			e.push_back(es[i].cost);
		}
	}
	
	for (int i = 0; i < C; i++){
		int B, H;
		scanf("%d %d", &B, &H);
		
		if (H < N - e.size()) printf("-1\n");
		else {
			H -= (N - e.size());
			int pos = upper_bound(e.begin(), e.end(), B) - e.begin();
			pos = max(pos, (int)e.size() - H);
			printf("%lld\n", sumEdge[pos] + (lint)(N - pos) * B);
		}
	}
	
	return (0);
}