oj.uz

Submission #26001

# Submission time Handle Problem Language Result Execution time Memory
26001 2017-06-25T18:20:46 Z abcdef6199 도로 건설 사업 (JOI13_construction) C++
100 / 100
 2023 ms 96600 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 96600 KB Output is correct
2 Correct 489 ms 96600 KB Output is correct
3 Correct 443 ms 96600 KB Output is correct
4 Correct 719 ms 96600 KB Output is correct
5 Correct 486 ms 96600 KB Output is correct
6 Correct 503 ms 96600 KB Output is correct
7 Correct 479 ms 96600 KB Output is correct
8 Correct 339 ms 96600 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1479 ms 96600 KB Output is correct
2 Correct 1469 ms 96600 KB Output is correct
3 Correct 1439 ms 96600 KB Output is correct
4 Correct 1406 ms 96600 KB Output is correct
5 Correct 1633 ms 96600 KB Output is correct
6 Correct 473 ms 96600 KB Output is correct
7 Correct 1616 ms 96600 KB Output is correct
8 Correct 873 ms 96600 KB Output is correct
9 Correct 776 ms 96600 KB Output is correct
10 Correct 766 ms 96600 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 983 ms 96600 KB Output is correct
2 Correct 1046 ms 96600 KB Output is correct
3 Correct 966 ms 96600 KB Output is correct
4 Correct 1213 ms 96600 KB Output is correct
5 Correct 836 ms 96600 KB Output is correct
6 Correct 996 ms 96600 KB Output is correct
7 Correct 773 ms 96600 KB Output is correct
8 Correct 843 ms 96600 KB Output is correct
9 Correct 913 ms 96600 KB Output is correct
10 Correct 866 ms 96600 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1879 ms 96600 KB Output is correct
2 Correct 1349 ms 96600 KB Output is correct
3 Correct 1959 ms 96600 KB Output is correct
4 Correct 1016 ms 96600 KB Output is correct
5 Correct 2023 ms 96600 KB Output is correct
6 Correct 979 ms 96600 KB Output is correct
7 Correct 1226 ms 96600 KB Output is correct
8 Correct 1856 ms 96600 KB Output is correct
9 Correct 1289 ms 96600 KB Output is correct
10 Correct 1103 ms 96600 KB Output is correct
11 Correct 959 ms 96600 KB Output is correct