Submission #377796

#	Time	Username	Problem	Language	Result	Execution time	Memory
377796		ngpin04	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	822 ms	42612 KiB

construction

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 2e5 + 5;

struct BIT {
	int n;
	vector <long long> bit;

	BIT(int _n) {
		n = _n;
		bit.assign(n + 5, 0);
	}

	void update(int pos, long long val) {
		for (; pos <= n; pos += pos & -pos)
			bit[pos] += val;
	}

	void update(int l, int r, long long val) {
		update(l, val);
		update(r + 1, -val);
	}

	long long getval(int pos) {
		long long res = 0;
		for (; pos > 0; pos -= pos & -pos)
			res += bit[pos];
		return res;
	}
};

struct DisJointSet {
	int n;
	vector <int> par;

	DisJointSet(int _n) {
		n = _n;
		par.assign(n + 5, -1);
	}

	int getpar(int u) {
		return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
	}

	bool join(int u, int v) {
		u = getpar(u);
		v = getpar(v);
		if (u == v)
			return false;
		if (par[u] > par[v])
			swap(u, v);
		par[u] += par[v];
		par[v] = u;
		return true;
	}
};

struct seg {
	int h, l, r;
	seg(){};
	seg(int _h, int _l, int _r) {
		h = _h;
		l = _l;
		r = _r;
	}

	bool operator < (const seg &s) const {
		return h < s.h;
	}
};

vector <int> adj[N];

pair <pair <int, int>, pair <int, int>> rec[N];
pair <int, int> a[N];
pair <int, int> b[N];
vector <pair <int, pair <int, int>>> edge;

long long sum[N];

int val[N];
int n,m,k;

int dis(int i, int j) {
	return abs(a[i].fi - a[j].fi) + abs(a[i].se - a[j].se); 
}

void compress() {
	vector <int> val;

	for (int i = 1; i <= n; i++) 
		val.push_back(a[i].fi);

	for (int i = 1; i <= m; i++) {
		val.push_back(rec[i].fi.fi);
		val.push_back(rec[i].se.fi);
	}

	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());

	for (int i = 1; i <= n; i++)
		b[i].fi = lower_bound(val.begin(), val.end(), a[i].fi) - val.begin() + 1;

	for (int i = 1; i <= m; i++) {
		rec[i].fi.fi = lower_bound(val.begin(), val.end(), rec[i].fi.fi) - val.begin() + 1;	
		rec[i].se.fi = lower_bound(val.begin(), val.end(), rec[i].se.fi) - val.begin() + 1;
	}

	val.clear();

	for (int i = 1; i <= n; i++) 
		val.push_back(a[i].se);

	for (int i = 1; i <= m; i++) {
		val.push_back(rec[i].fi.se);
		val.push_back(rec[i].se.se);
	}

	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());

	for (int i = 1; i <= n; i++)
		b[i].se = lower_bound(val.begin(), val.end(), a[i].se) - val.begin() + 1;

	for (int i = 1; i <= m; i++) {
		rec[i].fi.se = lower_bound(val.begin(), val.end(), rec[i].fi.se) - val.begin() + 1;	
		rec[i].se.se = lower_bound(val.begin(), val.end(), rec[i].se.se) - val.begin() + 1;
	}
}

void buildgraph() {
	BIT bit(n + 2 * m);

	vector <seg> s;

	for (int i = 1; i <= n; i++)
		s.push_back(seg(b[i].se, -i, b[i].fi));

	for (int i = 1; i <= m; i++) 
		s.push_back(seg(rec[i].se.se, rec[i].fi.fi, rec[i].se.fi));

	sort(s.begin(), s.end());

	for (seg sg : s) {
		// cout << sg.h << " " << sg.l << " " << sg.r << endl;
		int l = sg.l;
		int r = sg.r;
		if (l < 0) {
			int u = -l;
			long long v = bit.getval(r);
			if (v > 0)
				edge.push_back(mp(dis(u, v), mp(u, v)));

			bit.update(r, r, u - v);
		} else 
			bit.update(l, r, -1e9);
	}
	// cout << endl;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i].fi >> a[i].se;

	for (int i = 1; i <= m; i++) 
		cin >> rec[i].fi.fi >> rec[i].fi.se >> rec[i].se.fi >> rec[i].se.se;
	
	compress();
	buildgraph();
	for (int i = 1; i <= n; i++)
		swap(b[i].fi, b[i].se);

	for (int i = 1; i <= m; i++) {
		swap(rec[i].fi.fi, rec[i].fi.se);
		swap(rec[i].se.fi, rec[i].se.se);
	}
	buildgraph();

	int cnt = 0;
	DisJointSet dsu(n);
	
	sort(edge.begin(), edge.end());

	for (pair <int, pair <int, int>> e : edge) {
		int u = e.se.fi;
		int v = e.se.se;
		if (dsu.join(u, v)) {
			val[++cnt] = e.fi;
			 // cerr << u << " " << v << endl;
		}
	}

	for (int i = 1; i <= cnt; i++)
		sum[i] = sum[i - 1] + val[i];

	while (k--) {
		int cost,num;
		cin >> cost >> num;
		if (cnt + num < n) {
			cout << -1 << "\n";
			continue;
		}
		int lo = 0;
		int hi = cnt + 1;
		while (hi - lo > 1) {
			int mid = (lo + hi) >> 1;
			if (val[mid] < cost)
				lo = mid;
			else 
				hi = mid;
		}
		lo = max(lo, n - num);

		cout << (long long) (n - lo) * cost + sum[lo] << "\n";
	}
	return 0;
}

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