Submission #1189273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189273		JooDdae	도로 건설 사업 (JOI13_construction)	C++20	40 / 100	5093 ms	20748 KiB

construction

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

#define mid ((l+r) >> 1)

const ll INF = 1e18;

int n, m, c;

vector<int> X, Y;
int lb(const vector<int> &v, int k) {
	return lower_bound(v.begin(), v.end(), k) - v.begin();
}
int ub(const vector<int> &v, int k) {
	return upper_bound(v.begin(), v.end(), k) - v.begin();
}

int p[200200], cnt;
ll d[200200];
int find(int x) { return x == p[x] ? x : p[x] = find(p[x]); }
int merge(int x, int y) {
	if((x = find(x)) == (y = find(y))) return 0;
	p[x] = y;
	return 1;
}

int t[800800];
bool lz[800800];
void lazy_update(int node, int l, int r) {
	if(lz[node]) {
		if(l != r) lz[node*2] = lz[node*2+1] = 1;
		else t[node] = -1;
		lz[node] = 0;
	}
}
void update(int nl, int nr, int node = 1, int l = 0, int r = n-1) {
	lazy_update(node, l, r);
	if(nr < l || r < nl) return;
	if(nl <= l && r <= nr) {
		lz[node] = 1;
		lazy_update(node, l, r);
		return;
	}
	update(nl, nr, node*2, l, mid), update(nl, nr, node*2+1, mid+1, r);
}
int find(int x, int id, int node = 1, int l = 0, int r = n-1) {
	lazy_update(node, l, r);
	if(x < l || r < x) return -1;
	if(l == r) {
		int re = t[node];
		t[node] = id;
		return re;
	}
	return max(find(x, id, node*2, l, mid), find(x, id, node*2+1, mid+1, r));
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m >> c;
	vector<array<int, 3>> e(n);
	vector<int> xi(n), yi(n);
	for(int i=0;i<n;i++) {
		auto &[x, y, id] = e[i];
		cin >> x >> y; id = i;
		xi[i] = x, yi[i] = y;
	}
	for(auto &[x, y, i] : e) X.push_back(x), Y.push_back(y);
	sort(X.begin(), X.end()), X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end()), Y.erase(unique(Y.begin(), Y.end()), Y.end());
	for(auto &[x, y, i] : e) x = lb(X, x), y = lb(Y, y);

	vector<array<int, 4>> w(m);
	for(auto &[xl, yl, xr, yr] : w) cin >> xl >> yl >> xr >> yr;
	for(auto &[xl, yl, xr, yr] : w) xl = lb(X, xl), xr = ub(X, xr)-1;
	for(auto &[xl, yl, xr, yr] : w) yl = lb(Y, yl), yr = ub(Y, yr)-1;

	vector<array<int, 3>> E;

	for(int T=0;T<2;T++) {
		for(auto &[x, y, i] : e) swap(x, y);
		for(auto &[xl, yl, xr, yr] : w) swap(xl, yl), swap(xr, yr);
		for(int i=0;i<n;i++) swap(xi[i], yi[i]);

		memset(t, -1, sizeof t), memset(lz, 0, sizeof lz);

		sort(e.begin(), e.end()), sort(w.begin(), w.end());
		for(int i=0, j=0;i<n;i++) {
			auto [x, y, id] = e[i];
			while(j < m && w[j][0] <= x) update(w[j][1], w[j][3]), j++;
			int re = find(y, id);
			if(re != -1) E.push_back({xi[id]-xi[re], re, id});
		}
	}

	sort(E.begin(), E.end());
	iota(p, p+n, 0);
	for(auto [c, x, y] : E) if(merge(x, y)) cnt++, d[n-cnt] = d[n-cnt+1] + c;
	for(int i=cnt+1;i<n;i++) d[n-i] = INF + ll(1e11) * i;

	while(c--) {
		ll b; int h; cin >> b >> h;
		// int l = 1, r = h;
		// while(l < r+1) {
		// 	int m1 = (l+l+r)/3, m2 = (l+r+r)/3;
			
		// 	if(m1*b + d[m1] < m2*b + d[m2]) r = m2-1;
		// 	else l = m1+1;
		// }
		// ll ans = INF;
		// for(int i=max(1, l-5);i<=min(h, l+5);i++) ans = min(ans, i*b+d[i]);

		ll ans = INF;
		for(int i=1;i<=h;i++) ans = min(ans, i*b+d[i]);
		cout << (ans == INF ? -1 : ans)  << "\n";
	}
}

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