oj.uz

Submission #145298

# Submission time Handle Problem Language Result Execution time Memory
145298 2019-08-19T14:16:23 Z maruii 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1840 ms 111288 KB 
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second
#define eack emplace_back
#define pack push_back

vector<int> xx, yy;
vector<pii> in, xnode[600005], ynode[600005];
vector<pair<pii, pii> > in2, xsp, ysp;
long long W[200005];

int upa[200005];
int fnd(int x) {return upa[x] == x ? x : upa[x] = fnd(upa[x]);}
bool uni(int x, int y) {
	x = fnd(x), y = fnd(y);
	if (x == y) return 0;
	upa[y] = x;
	return 1;
}

const int SIZE = 1 << 20;
struct ST {
	int V[2 * SIZE], L[2 * SIZE];
	int sz;
	void init() {
		memset(V, 0, sizeof(V));
		memset(L, 0, sizeof(L));
	}
	void Ldown(int nn, int s, int m, int e) {
		L[nn << 1] += L[nn];
		L[nn << 1 | 1] += L[nn];
		V[nn << 1] += L[nn];
		V[nn << 1 | 1] += L[nn];
		L[nn] = 0;
	}
	void update(int s, int e, int v, int nn, int ns, int ne) {
		if (ns > e || ne < s) return;
		if (s <= ns && ne <= e) {
			V[nn] += v;
			L[nn] += v;
			return;
		}
		int m = ns + ne >> 1;
		Ldown(nn, ns, m, ne);
		update(s, e, v, nn << 1, ns, m);
		update(s, e, v, nn << 1 | 1, m + 1, ne);
		V[nn] = max(V[nn << 1], V[nn << 1 | 1]);
	}
	int query(int s, int e, int nn, int ns, int ne) {
		if (ns > e || ne < s) return 0;
		if (s <= ns && ne <= e) return V[nn];
		int m = ns + ne >> 1;
		Ldown(nn, ns, m, ne);
		return max(query(s, e, nn << 1, ns, m), query(s, e, nn << 1 | 1, m + 1, ne));
	}
	void update(int s, int e, int v) {
		update(s, e, v, 1, 0, sz);
	}
	int query(int s, int e) {
		return query(s, e, 1, 0, sz);
	}
} seg;

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N, M, C; cin >> N >> M >> C;
	for (int i = 0; i < N; ++i) {
		int x, y; cin >> x >> y;
		xx.eack(x);
		yy.eack(y);
		in.eack(x, y);
	}
	
	for (int i = 0; i < M; ++i) {
		int p, q, r, s; cin >> p >> q >> r >> s;
		xx.eack(p); xx.eack(r);
		yy.eack(q); yy.eack(s);
		in2.eack(pii(p, q), pii(r, s));
	}	
		
	sort(xx.begin(), xx.end());
	sort(yy.begin(), yy.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	yy.erase(unique(yy.begin(), yy.end()), yy.end());
	iota(upa, upa + N, 0);

	for (int ii = 0; ii < in.size(); ++ii) {
		auto i = in[ii];
		i.ff = lower_bound(xx.begin(), xx.end(), i.ff) - xx.begin();
		i.ss = lower_bound(yy.begin(), yy.end(), i.ss) - yy.begin();
		xnode[i.ff].eack(i.ss, ii);
		ynode[i.ss].eack(i.ff, ii);
	}
	
	for (int i = 0; i < xx.size(); ++i) sort(xnode[i].begin(), xnode[i].end());
	for (int i = 0; i < yy.size(); ++i) sort(ynode[i].begin(), ynode[i].end());

	for (auto i : in2) {
		int p, q, r, s;
		tie(p, q) = i.ff;
		tie(r, s) = i.ss;
		p = lower_bound(xx.begin(), xx.end(), p) - xx.begin();
		r = lower_bound(xx.begin(), xx.end(), r) - xx.begin();
		q = lower_bound(yy.begin(), yy.end(), q) - yy.begin();
		s = lower_bound(yy.begin(), yy.end(), s) - yy.begin();
		xsp.eack(pii(p, 1), pii(q, s));
		xsp.eack(pii(r + 1, -1), pii(q, s));
		ysp.eack(pii(q, 1), pii(p, r));
		ysp.eack(pii(s + 1, -1), pii(p, r));
	}
	
	sort(xsp.begin(), xsp.end());
	sort(ysp.begin(), ysp.end());

	vector<pair<int, pii> > E;
	seg.sz = (int)yy.size() - 1;

	for (int i = 0, si = 0; i < xx.size(); ++i) {
		for (; si < xsp.size() && xsp[si].ff.ff <= i; ++si) {
			seg.update(xsp[si].ss.ff, xsp[si].ss.ss, xsp[si].ff.ss);
		}
		
		auto &vec = xnode[i];
		for (int j = 0; j + 1 < vec.size(); ++j) {
			if (seg.query(vec[j].ff, vec[j + 1].ff) == 0) {
				E.eack(yy[vec[j + 1].ff] - yy[vec[j].ff], pii(vec[j].ss, vec[j + 1].ss));
			}
		}
	}

	seg.init();
	seg.sz = (int)xx.size() - 1;

	for (int i = 0, si = 0; i < yy.size(); ++i) {
		for (; si < ysp.size() && ysp[si].ff.ff <= i; ++si) {
			seg.update(ysp[si].ss.ff, ysp[si].ss.ss, ysp[si].ff.ss);
		}

		auto &vec = ynode[i];
		for (int j = 0; j + 1 < vec.size(); ++j) {
			if (seg.query(vec[j].ff, vec[j + 1].ff) == 0) {
				E.eack(xx[vec[j + 1].ff] - xx[vec[j].ff], pii(vec[j].ss, vec[j + 1].ss));
			}
		}
	}

	sort(E.begin(), E.end());
	int K = N;
	for (auto i : E) {
		if (uni(i.ss.ff, i.ss.ss)) {
			--K;
			W[K] = W[K + 1] + i.ff;
		}
	}

	vector<pair<pii, int> > qry(C);
	vector<long long> ans(C);
	
	for (int i = 0; i < C; ++i) {
		int a, b; cin >> a >> b;
		qry[i] = {pii(a, b), i};
	}
	
	sort(qry.begin(), qry.end());

	for (int i = 0, k = N; i < C; ++i) {
		if (qry[i].ff.ss < K) {
			ans[qry[i].ss] = -1;
			continue;
		}
		int a, b; tie(a, b) = qry[i].ff;
		while (k > K && a >= W[k - 1] - W[k]) --k;
		ans[qry[i].ss] = W[min(b, k)] + 1ll * min(b, k) * a;
	}
	
	for (auto i : ans) cout << i << '\n';
	return 0;
}

Compilation message

construction.cpp: In member function 'void ST::update(int, int, int, int, int, int)':
construction.cpp:45:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
construction.cpp: In member function 'int ST::query(int, int, int, int, int)':
construction.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = ns + ne >> 1;
           ~~~^~~~
construction.cpp: In function 'int main()':
construction.cpp:89:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int ii = 0; ii < in.size(); ++ii) {
                   ~~~^~~~~~~~~~~
construction.cpp:97:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < xx.size(); ++i) sort(xnode[i].begin(), xnode[i].end());
                  ~~^~~~~~~~~~~
construction.cpp:98:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < yy.size(); ++i) sort(ynode[i].begin(), ynode[i].end());
                  ~~^~~~~~~~~~~
construction.cpp:120:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, si = 0; i < xx.size(); ++i) {
                          ~~^~~~~~~~~~~
construction.cpp:121:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; si < xsp.size() && xsp[si].ff.ff <= i; ++si) {
          ~~~^~~~~~~~~~~~
construction.cpp:126:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vec.size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~
construction.cpp:136:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0, si = 0; i < yy.size(); ++i) {
                          ~~^~~~~~~~~~~
construction.cpp:137:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; si < ysp.size() && ysp[si].ff.ff <= i; ++si) {
          ~~~^~~~~~~~~~~~
construction.cpp:142:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j + 1 < vec.size(); ++j) {
                   ~~~~~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 46448 KB Output is correct
2 Correct 447 ms 64344 KB Output is correct
3 Correct 432 ms 64084 KB Output is correct
4 Correct 372 ms 63568 KB Output is correct
5 Correct 457 ms 65996 KB Output is correct
6 Correct 436 ms 64232 KB Output is correct
7 Correct 219 ms 63440 KB Output is correct
8 Correct 308 ms 66000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1614 ms 79636 KB Output is correct
2 Correct 1603 ms 87356 KB Output is correct
3 Correct 1656 ms 87500 KB Output is correct
4 Correct 1701 ms 87360 KB Output is correct
5 Correct 914 ms 85540 KB Output is correct
6 Correct 501 ms 66000 KB Output is correct
7 Correct 1583 ms 87252 KB Output is correct
8 Correct 642 ms 92964 KB Output is correct
9 Correct 647 ms 92972 KB Output is correct
10 Correct 763 ms 90680 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 696 ms 82696 KB Output is correct
2 Correct 694 ms 81224 KB Output is correct
3 Correct 675 ms 79180 KB Output is correct
4 Correct 605 ms 81188 KB Output is correct
5 Correct 650 ms 75604 KB Output is correct
6 Correct 691 ms 81660 KB Output is correct
7 Correct 680 ms 79952 KB Output is correct
8 Correct 686 ms 79312 KB Output is correct
9 Correct 448 ms 77740 KB Output is correct
10 Correct 546 ms 79480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1825 ms 94948 KB Output is correct
2 Correct 1179 ms 95288 KB Output is correct
3 Correct 1807 ms 106232 KB Output is correct
4 Correct 671 ms 80596 KB Output is correct
5 Correct 1832 ms 106640 KB Output is correct
6 Correct 714 ms 82240 KB Output is correct
7 Correct 1727 ms 111288 KB Output is correct
8 Correct 1840 ms 110900 KB Output is correct
9 Correct 900 ms 107340 KB Output is correct
10 Correct 1006 ms 109920 KB Output is correct
11 Correct 579 ms 88228 KB Output is correct