Submission #26001

#	Time	Username	Problem	Language	Result	Execution time	Memory
26001		abcdef6199	도로 건설 사업 (JOI13_construction)	C++98	100 / 100	2023 ms	96600 KiB

construction

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int, int> II;
struct Point {
	int x, y, i;
	Point() {};
	Point(int x, int y, int i): x(x), y(y), i(i) {};
};
struct Edge {
	int u, v, w;
	Edge() {};
	Edge(int u, int v, int w): u(u), v(v), w(w) {};
	bool operator < (const Edge &E) const {
		return w < E.w;
	}
};
struct Rectangle {
	int x1, y1, x2, y2;	
};

const int N = (int) 8e5 + 10;
int n, m, k, q, x[N], y[N];
Point P[N];
Edge E[N];
Rectangle R[N];

int E_v[N];
int E_h[N];
int tx[N];
int ty[N];
int p[N];
bool mark[N];
int com_count[N];
LL  sum_edges[N];

int Root(int u) {
	if (p[u] < 0) return u;
	return p[u] = Root(p[u]);
}

int Merge(int u, int v) {
	u = Root(u);
	v = Root(v);
	if (u == v) return 0;
	if (p[u] > p[v]) swap(u, v);
	p[u] += p[v]; p[v] = u;
	return 1;
}

bool cmp_by_X(Point A, Point B) { return A.x < B.x || (A.x == B.x && A.y < B.y); }
bool cmp_by_Y(Point A, Point B) { return A.y < B.y || (A.y == B.y && A.x < B.x); }

void InitEdge() {
	sort(P + 1, P + 1 + n, cmp_by_X);
	for (int i = 1; i <= n; ++i) {
		int j = i;
		while (j < n && P[j + 1].x == P[i].x) j++;
		for (int t = i; t <= j - 1; ++t) {
			int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
			E[++m] = Edge(P[t].i, P[t + 1].i, w);
		}
		i = j;
	}
	sort(P + 1, P + 1 + n, cmp_by_Y);
	for (int i = 1; i <= n; ++i) {
		int j = i;
		while (j < n && P[j + 1].y == P[i].y) j++;
		for (int t = i; t <= j - 1; ++t) {
			int w = abs(P[t].x - P[t + 1].x) + abs(P[t].y - P[t + 1].y);
			E[++m] = Edge(P[t].i, P[t + 1].i, w);
		}
		i = j;
	}
	sort(E + 1, E + 1 + m);
}

bool cmp_by_x1(Rectangle A, Rectangle B) { return A.x1 < B.x1; }
bool cmp_by_y1(Rectangle A, Rectangle B) { return A.y1 < B.y1; }
bool cmpv(int a, int b) { return x[E[a].u] < x[E[b].u]; }
bool cmph(int a, int b) { return y[E[a].u] < y[E[b].u]; }

#define mid ((l + r) >> 1)
struct SegTree {
	int S[N * 5];
	int L[N * 5];
	void Init(int k, int l, int r) {
		if (l == r) {
			S[k] = -1;
			L[k] = -1;
			return;
		}
		Init(k << 1 | 0, l, mid);
		Init(k << 1 | 1, mid + 1, r);
		S[k] = -1;
		L[k] = -1;
	}
	void Maximize(int &a, int v) { a = max(a, v); }
	void Propagate(int k) {
		int v = L[k]; L[k] = -1; if (v == -1) return;
		Maximize(S[k << 1 | 0], v); Maximize(L[k << 1 | 0], v);
		Maximize(S[k << 1 | 1], v); Maximize(L[k << 1 | 1], v);
	}
	void Update(int k, int l, int r, int i, int j, int v) {
		if (l > j || r < i) return;
		if (i <= l && r <= j) {
			Maximize(S[k], v);
			Maximize(L[k], v);
			return;
		}
		Propagate(k);
		Update(k << 1 | 0, l, mid, i, j, v);
		Update(k << 1 | 1, mid + 1, r, i, j, v);
		S[k] = max(S[k << 1], S[k << 1 | 1]);
	}
	int Query(int k, int l, int r, int i, int j) {
		if (l > j || r < i) return -1;
		if (i <= l && r <= j) return S[k];
		Propagate(k);
		return max(Query(k << 1, l, mid, i, j),
		           Query(k << 1 | 1, mid + 1, r, i, j));
	}
} ST;
#undef mid

int main() {
	scanf("%d%d%d", &n, &k, &q);
	for (int i = 1; i <= n; ++i) {
		scanf("%d%d", &x[i], &y[i]);
		P[i] = Point(x[i], y[i], i);
		tx[i] = x[i];
		ty[i] = y[i];
	}
	InitEdge();

	for (int i = 1; i <= m; ++i) mark[i] = true;
	for (int i = 1; i <= k; ++i) {
		scanf("%d%d", &R[i].x1, &R[i].y1);
		scanf("%d%d", &R[i].x2, &R[i].y2);
		tx[n + i * 2 - 1] = R[i].x1;
		tx[n + i * 2 - 0] = R[i].x2;
		ty[n + i * 2 - 1] = R[i].y1;
		ty[n + i * 2 - 0] = R[i].y2;
	}

	int ch = 0, cv = 0;
	for (int i = 1; i <= m; ++i) {
		int u = E[i].u;
		int v = E[i].v;
		if (x[u] == x[v]) E_v[++cv] = i;
		else E_h[++ch] = i;
	}
	sort(E_v + 1, E_v + 1 + cv, cmpv);
	sort(E_h + 1, E_h + 1 + ch, cmph);
	sort(tx + 1, tx + 1 + n + k * 2);
	sort(ty + 1, ty + 1 + n + k * 2);

	ST.Init(1, 1, n + k * 2);
	sort(R + 1, R + 1 + k, cmp_by_x1);
	for (int i = 1, j = 0; i <= cv; ++i) {
		int u = E[E_v[i]].u;
		int v = E[E_v[i]].v;
		while (j < k && R[j + 1].x1 <= x[u]) {
			j++;
			int l = lower_bound(ty + 1, ty + 1 + n + k * 2, R[j].y1) - ty;
			int r = upper_bound(ty + 1, ty + 1 + n + k * 2, R[j].y2) - ty - 1;
			if (l <= r) ST.Update(1, 1, n + k * 2, l, r, R[j].x2);
		}
		int l = lower_bound(ty + 1, ty + 1 + n + k * 2, y[u]) - ty;
		int r = lower_bound(ty + 1, ty + 1 + n + k * 2, y[v]) - ty;
		mark[E_v[i]] &= ST.Query(1, 1, n + k * 2, l, r) < x[u];
	}

	ST.Init(1, 1, n + k * 2);
	sort(R + 1, R + 1 + k, cmp_by_y1);
	for (int i = 1, j = 0; i <= ch; ++i) {
		int u = E[E_h[i]].u;
		int v = E[E_h[i]].v;
		while (j < k && R[j + 1].y1 <= y[u]) {
			j++;
			int l = lower_bound(tx + 1, tx + 1 + n + k * 2, R[j].x1) - tx;
			int r = upper_bound(tx + 1, tx + 1 + n + k * 2, R[j].x2) - tx - 1;
			if (l <= r) ST.Update(1, 1, n + k * 2, l, r, R[j].y2);
		}
		int l = lower_bound(tx + 1, tx + 1 + n + k * 2, x[u]) - tx;
		int r = lower_bound(tx + 1, tx + 1 + n + k * 2, x[v]) - tx;
		mark[E_h[i]] &= ST.Query(1, 1, n + k * 2, l, r) < y[u];
	}

	// for (int i = 1; i <= m; ++i) printf("%d ", mark[i]); puts("");

	// for (int i = 1; i <= m; ++i) mark[i] = true;
	// for (int i = 1; i <= k; ++i) {
	// 	int x1, y1; scanf("%d%d", &x1, &y1);
	// 	int x2, y2; scanf("%d%d", &x2, &y2);
	// 	for (int j = 1; j <= m; ++j) {
	// 		int u = E[j].u;
	// 		int v = E[j].v;
	// 		if (x[u] == x[v] && x1 <= x[u] && x[u] <= x2) {
	// 			if (max(y[u], y1) <= min(y[v], y2)) mark[j] = false;
	// 		}
	// 		if (y[u] == y[v] && y1 <= y[u] && y[u] <= y2) {
	// 			if (max(x[u], x1) <= min(x[v], x2)) mark[j] = false;
	// 		}
	// 	}
	// }

	for (int i = 1; i <= n; ++i) p[i] = -1; com_count[0] = n;
	for (int i = 1; i <= m; ++i) {
		int u = E[i].u;
		int v = E[i].v;
		com_count[i] = com_count[i - 1];
		sum_edges[i] = sum_edges[i - 1];
		if (mark[i] && Merge(u, v)) {
			com_count[i] -= 1;
			sum_edges[i] += E[i].w;
		}
	}

	while (q--) {
		int a, b; scanf("%d%d", &a, &b);
		int l = 1, r = m, f = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (com_count[mid] <= b) {
				f = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		LL ans = (LL) 1e18;
		if (f != -1) ans = min(ans, sum_edges[f] + (LL) a * b);

		l = 1; r = m; f = 0;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (E[mid].w <= a) {
				f = mid;
				l = mid + 1;
			}
			else r = mid - 1;
		}
		if (com_count[f] <= b) ans = min(ans, sum_edges[f] + (LL) a * com_count[f]);
		if (ans == (LL) 1e18) ans = -1;
		printf("%lld\n", ans);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:128:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &q);
                             ^
construction.cpp:130:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x[i], &y[i]);
                              ^
construction.cpp:139:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &R[i].x1, &R[i].y1);
                                    ^
construction.cpp:140:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &R[i].x2, &R[i].y2);
                                    ^
construction.cpp:222:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a, b; scanf("%d%d", &a, &b);
                                  ^

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30