oj.uz

Submission #283706

# Submission time Handle Problem Language Result Execution time Memory
283706 2020-08-26T05:53:55 Z 임성재(#5753) 도로 건설 사업 (JOI13_construction) C++17
40 / 100
 2522 ms 197708 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 1e18;
const ll inf = 1e9;

int n, m, c;
vector<int> v;
vector<pii> e;
int x[200010];
int y[200010];
int p[200010];
int q[200010];
int r[200010];
int s[200010];
int par[200010];
ll sum[200010];
vector<ll> ans;
vector<int> com;
vector<pii> qr[2][1000010];

int tree[4000010];
int lazy[4000010];

void propagate(int node, int s, int e) {
	if(!lazy[node]) return;

	tree[node] += lazy[node];

	if(s != e) {
		lazy[node*2] += lazy[node];
		lazy[node*2+1] += lazy[node];
	}

	lazy[node] = 0;
}

void update(int node, int s, int e, int l, int r, int x) {
	propagate(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		lazy[node] += x;
		propagate(node, s, e);
		return;
	}

	update(node*2, s, (s+e)/2, l, r, x);
	update(node*2+1, (s+e)/2+1, e, l, r, x);

	tree[node] = max(tree[node*2], tree[node*2+1]);
}

int cal(int node, int s, int e, int l, int r) {
	propagate(node, s, e);

	if(r < s || e < l) return 0;
	if(l <= s && e <= r) return tree[node];

	return max(cal(node*2, s, (s+e)/2, l, r), cal(node*2+1, (s+e)/2+1, e, l, r));
}

int Find(int a) { return par[a] = par[a] == a ? a : Find(par[a]); }
void Union(int a, int b) { par[Find(b)] = Find(a); }

int main() {
	fast;

	cin >> n >> m >> c;

	for(int i=1; i<=n; i++) {
		cin >> x[i] >> y[i];
		v.eb(i);
		par[i] = i;

		com.eb(x[i]);
		com.eb(y[i]);
	}

	for(int i=1; i<=m; i++) {
		cin >> p[i] >> q[i] >> r[i] >> s[i];

		com.eb(p[i]);
		com.eb(q[i]);
		com.eb(r[i]);
		com.eb(s[i]);
	}

	sort(all(com));
	com.erase(unique(all(com)), com.end());

	for(int i=1; i<=m; i++) {
		p[i] = lower_bound(all(com), p[i]) - com.begin();
		q[i] = lower_bound(all(com), q[i]) - com.begin();
		r[i] = lower_bound(all(com), r[i]) - com.begin();
		s[i] = lower_bound(all(com), s[i]) - com.begin();

		qr[0][p[i]].eb(i, 1);
		qr[0][r[i]+1].eb(i, -1);

		qr[1][q[i]].eb(i, 1);
		qr[1][s[i]+1].eb(i, -1);
	}

	sort(all(v), [&](int i, int j) { return mp(x[i], y[i]) < mp(x[j], y[j]); });

	int cur = 0;

	for(int i=1; i<v.size(); i++) {
		while(cur < com.size() && com[cur] <= x[v[i]]) {
			for(auto j : qr[0][cur]) {
				update(1, 0, com.size(), q[j.fi], s[j.fi], j.se);
			}

			cur++;
		}

		int L = lower_bound(all(com), y[v[i-1]]) - com.begin();
		int R = lower_bound(all(com), y[v[i]]) - com.begin();

		if(x[v[i]] == x[v[i-1]] && !cal(1, 0, com.size(), L, R)) {
			e.eb(v[i-1], v[i]);
		}
	}

	while(cur <= com.size()) {
		for(auto j : qr[0][cur]) {
			update(1, 0, com.size(), q[j.fi], s[j.fi], j.se);
		}

		cur++;
	}

	sort(all(v), [&](int i, int j) { return mp(y[i], x[i]) < mp(y[j], x[j]); });

	cur = 0;
	for(int i=1; i<v.size(); i++) {
		while(cur < com.size() && com[cur] <= y[v[i]]) {
			for(auto j : qr[1][cur]) {
				update(1, 0, com.size(), p[j.fi], r[j.fi], j.se);
			}

			cur++;
		}

		int L = lower_bound(all(com), x[v[i-1]]) - com.begin();
		int R = lower_bound(all(com), x[v[i]]) - com.begin();

		if(y[v[i]] == y[v[i-1]] && !cal(1, 0, com.size(), L, R)) {
			e.eb(v[i-1], v[i]);
		}
	}


	sort(all(e), [&](pii i, pii j) {
		return abs(x[i.fi] - x[i.se] + y[i.fi] - y[i.se]) < abs(x[j.fi] - x[j.se] + y[j.fi] - y[j.se]);
	});

	for(auto i : e) {
		if(Find(i.fi) == Find(i.se)) continue;

		Union(i.fi, i.se);
		ans.eb(abs(x[i.fi] - x[i.se] + y[i.fi] - y[i.se]));
	}

	sort(all(ans));

	for(int i=0; i<ans.size(); i++) {
		sum[i+1] = sum[i] + ans[i];
	}

	while(c--) {
		ll b, h;
		cin >> b >> h;

		ll k = upper_bound(all(ans), b) - ans.begin();

		k = max(k, n - h);

		if(k <= ans.size()) {
			cout << sum[k] + (n - k) * b << "\n";
		}
		else cout << "-1\n";
	}
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:119:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:120:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |   while(cur < com.size() && com[cur] <= x[v[i]]) {
      |         ~~~~^~~~~~~~~~~~
construction.cpp:136:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |  while(cur <= com.size()) {
      |        ~~~~^~~~~~~~~~~~~
construction.cpp:147:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for(int i=1; i<v.size(); i++) {
      |               ~^~~~~~~~~
construction.cpp:148:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |   while(cur < com.size() && com[cur] <= y[v[i]]) {
      |         ~~~~^~~~~~~~~~~~
construction.cpp:178:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |  for(int i=0; i<ans.size(); i++) {
      |               ~^~~~~~~~~~~
construction.cpp:190:8: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |   if(k <= ans.size()) {
      |      ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48760 KB Output is correct
2 Correct 492 ms 58464 KB Output is correct
3 Correct 494 ms 58204 KB Output is correct
4 Correct 447 ms 60472 KB Output is correct
5 Correct 556 ms 57188 KB Output is correct
6 Correct 523 ms 58204 KB Output is correct
7 Correct 259 ms 60384 KB Output is correct
8 Correct 300 ms 58588 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48760 KB Output is correct
2 Correct 492 ms 58464 KB Output is correct
3 Correct 494 ms 58204 KB Output is correct
4 Correct 447 ms 60472 KB Output is correct
5 Correct 556 ms 57188 KB Output is correct
6 Correct 523 ms 58204 KB Output is correct
7 Correct 259 ms 60384 KB Output is correct
8 Correct 300 ms 58588 KB Output is correct
9 Correct 2506 ms 97356 KB Output is correct
10 Correct 2522 ms 97556 KB Output is correct
11 Runtime error 2486 ms 197708 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48760 KB Output is correct
2 Correct 492 ms 58464 KB Output is correct
3 Correct 494 ms 58204 KB Output is correct
4 Correct 447 ms 60472 KB Output is correct
5 Correct 556 ms 57188 KB Output is correct
6 Correct 523 ms 58204 KB Output is correct
7 Correct 259 ms 60384 KB Output is correct
8 Correct 300 ms 58588 KB Output is correct
9 Correct 758 ms 65800 KB Output is correct
10 Correct 758 ms 63756 KB Output is correct
11 Correct 717 ms 62816 KB Output is correct
12 Correct 591 ms 64596 KB Output is correct
13 Correct 628 ms 60244 KB Output is correct
14 Correct 731 ms 63340 KB Output is correct
15 Correct 742 ms 65760 KB Output is correct
16 Correct 730 ms 65248 KB Output is correct
17 Correct 439 ms 65488 KB Output is correct
18 Correct 528 ms 63576 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 48760 KB Output is correct
2 Correct 492 ms 58464 KB Output is correct
3 Correct 494 ms 58204 KB Output is correct
4 Correct 447 ms 60472 KB Output is correct
5 Correct 556 ms 57188 KB Output is correct
6 Correct 523 ms 58204 KB Output is correct
7 Correct 259 ms 60384 KB Output is correct
8 Correct 300 ms 58588 KB Output is correct
9 Correct 2506 ms 97356 KB Output is correct
10 Correct 2522 ms 97556 KB Output is correct
11 Runtime error 2486 ms 197708 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -