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); }