Submission #49488

#	Time	Username	Problem	Language	Result	Execution time	Memory
49488		minkank	도로 건설 사업 (JOI13_construction)	C++17	0 / 100	1030 ms	98040 KiB

construction

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

#define int long long
#define data Data

typedef pair<int, int> ii;
typedef pair<int, ii> II;
#define x first
#define y second

const int N = 5e5 + 5;

struct data {
	int x, y, x2, y2;
};

int n, m, c, par[N];
long long f[N];
II qu[N * 2];
data p[N * 2];
vector<II> E;

bool cmp(data u, data v) {
	return u.x < v.x;
}

void sweep() {
	sort(p + 1, p + n + m + 1, cmp);
	set<ii> s;
	for(int i = 1; i <= n + m; ++i) {
		if(p[i].x2 < 0) {
			set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
			if(it != s.end() && (*it).x == p[i].y) {
				int id = (*it).y;
				E.push_back(II(p[i].x - p[id].x, ii(-p[id].x2, -p[i].x2)));
				s.erase(it);
			}
			s.insert(ii(p[i].y, i));
		}
		else {
			while(1) {
				set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
				if(it == s.end() || (*it).x > p[i].y2) break;
				s.erase(it);
			}
		}
	}
}

void reverse() {
	for(int i = 1; i <= n + m; ++i) {
		swap(p[i].x, p[i].x2);
		swap(p[i].y, p[i].y2);
	}
}

int find(int u) {
	if(par[u] == u) return u;
	return par[u] = find(par[u]);
}

bool join(int u, int v) {
	u = find(u); v = find(v);
	if(u == v) return false;
	par[u] = v;
	return true;
}

vector<ii> d;

bool bad(int l1, int l2, int l3) {
	return 1LL * (d[l2].y - d[l1].y) * (d[l3].x - d[l2].x) > 1LL * (d[l3].y - d[l2].y) * (d[l2].x - d[l1].x);
}
 
void add(int a, long long b) {
	d.push_back(ii(a, b));
	while(d.size() >= 3 && !bad(d.size() - 1, d.size() - 2, d.size() - 3)) d.erase(d.end() - 2);
}
 
long long query(int x) {
	int l = 0, r = d.size() - 1;
	while(l != r) {
		int mid = (l + r) >> 1;
		if(1LL * d[mid].x * x + d[mid].y > 1LL * d[mid + 1].x * x + d[mid + 1].y) l = mid + 1;
		else r = mid;
	}
	return 1LL * d[l].x * x + d[l].y;
}

long long ans[N];

signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> c;
	for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y, p[i].x2 = p[i].y2 = -i;
	for(int i = 1; i <= m; ++i) cin >> p[i + n].x >> p[i + n].y >> p[i + n].x >> p[i + n].y;
	sweep();
	reverse();
	sweep();
	sort(E.begin(), E.end());
	int tot = 0;
	vector<int> E2;
	for(int i = 1; i <= n; ++i) par[i] = i;
	for(int i = E.size() - 1; i >= 0; --i) {
		int w = E[i].x, u = E[i].y.x, v = E[i].y.y;
		if(join(u, v)) E2.push_back(w), tot += w;
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i) if(find(i) == i) cnt++;
	memset(f, 69, sizeof f);
	f[cnt] = tot;
	for(int i = 0; i < E2.size(); ++i) {
		tot -= E2[i];
		f[cnt + 1 + i] = tot;
	}
	for(int i = 1; i <= c; ++i) cin >> qu[i].y.x >> qu[i].x, qu[i].y.y = i;
	for(int i = 1; i <= n; ++i) qu[i + c].x = i, qu[i + c].y.y = -1;
	sort(qu + 1, qu + n + c + 1);
	for(int i = 1; i <= n + c; ++i) {
		if(qu[i].y.y < 0) {
			add(qu[i].x, f[qu[i].x]);
		}
		else {
			ans[qu[i].y.y] = query(qu[i].y.x);
		}
	}
	for(int i = 1; i <= c; ++i) {
		if(ans[i] > 1e18) ans[i] = -1;
		cout << ans[i] << '\n';
	}
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:113:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < E2.size(); ++i) {
                 ~~^~~~~~~~~~~

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