oj.uz

Submission #287074

# Submission time Handle Problem Language Result Execution time Memory
287074 2020-08-31T11:28:35 Z cki86201 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 1690 ms 83768 KB 
#include <bits/stdc++.h>
using namespace std;

#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;

const int INF = 1e9;

struct tree {
	static const int L = 1 << 20;
	int T[L*2], C[L*2];
	void add_node(int rt, int x) {
		T[rt] += x;
		C[rt] += x;
	}
	void pushdown(int rt) {
		if(C[rt]) {
			add_node(rt*2, C[rt]);
			add_node(rt*2+1, C[rt]);
			C[rt] = 0;
		}
	}
	void update(int s, int e, int x, int rt = 1, int l = 0, int r = L-1) {
		if(s <= l && r <= e) {
			add_node(rt, x);
			return;
		}
		pushdown(rt);
		int m = (l + r) >> 1;
		if(s <= m) update(s, e, x, rt*2, l, m);
		if(m < e) update(s, e, x, rt*2+1, m+1, r);
		T[rt] = max(T[rt*2], T[rt*2+1]);
	}
	int Read(int s, int e, int rt = 1, int l = 0, int r = L-1) {
		if(s <= l && r <= e) return T[rt];
		pushdown(rt);
		int m = (l + r) >> 1, res = 0;
		if(s <= m) res = max(res, Read(s, e, rt*2, l, m));
		if(m < e) res = max(res, Read(s, e, rt*2+1, m+1, r));
		return res;
	}
	void init() {
		memset(T, 0, sizeof T);
		memset(C, 0, sizeof C);
	}
} tree;

int N, M, C;
struct rect {
	int x1, y1, x2, y2;
} R[200020];
struct point {
	int x, y, id;
} P[200020];
struct event {
	int x, y1, y2, i1, i2;
};
vector <t3> E;

void Do(vector <int> &vy) {
	sort(P+1, P+1+N, [](point a, point b) { return tie(a.x, a.y) < tie(b.x, b.y); });
	vector <event> V;
	for(int i=1;i<N;i++) if(P[i].x == P[i+1].x) {
		V.pb({P[i].x, P[i].y, P[i+1].y, P[i].id, P[i+1].id});
	}
	for(int i=1;i<=M;i++) {
		V.pb({R[i].x1, R[i].y1, R[i].y2, -1, 0});
		V.pb({R[i].x2, R[i].y1, R[i].y2, INF, 0});
	}
	sort(all(V), [](const event &a, const event &b) { return tie(a.x, a.i1) < tie(b.x, b.i1); });
	tree.init();
	for(auto &[x, y1, y2, i1, i2] : V) {
		if(i1 == -1) tree.update(y1, y2, 1);
		else if(i1 == INF) tree.update(y1, y2, -1);
		else {
			int v = tree.Read(y1, y2);
			if(v == 0) E.pb({vy[y2] - vy[y1], i1, i2});
		}
	}
}

int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }

int main() {
	scanf("%d%d%d", &N, &M, &C);
	vector <int> vx, vy;
	for(int i=1;i<=N;i++) {
		int x, y; scanf("%d%d", &x, &y);
		P[i] = {x, y, i};
		vx.pb(x); vy.pb(y);
	}
	for(int i=1;i<=M;i++) {
		int x1, y1, x2, y2;
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		R[i] = {x1, y1, x2, y2};
		vx.pb(x1), vx.pb(x2);
		vy.pb(y1), vy.pb(y2);
	}
	sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
	sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
	auto fix = [](vector <int> &a, int &b) {
		b = (int)(lower_bound(all(a), b) - a.begin());
	};
	for(int i=1;i<=N;i++) fix(vx, P[i].x), fix(vy, P[i].y);
	for(int i=1;i<=M;i++) {
		fix(vx, R[i].x1), fix(vx, R[i].x2);
		fix(vy, R[i].y1), fix(vy, R[i].y2);
	}
	rep(v, 2) {
		Do(v == 0 ? vy : vx);
		for(int i=1;i<=M;i++) {
			swap(R[i].x1, R[i].y1);
			swap(R[i].x2, R[i].y2);
		}
		for(int i=1;i<=N;i++) swap(P[i].x, P[i].y);
	}
	sort(all(E));
	for(int i=1;i<=N;i++) pp[i] = i;
	vector <int> V;
	vector <ll> SV;
	for(auto &[l, x, y] : E) {
		int px = Find(x), py = Find(y);
		if(px != py) V.pb(l), pp[px] = py;
	}
	int lv = szz(V);
	SV.resize(lv);
	rep(i, lv) SV[i] = (i ? SV[i-1] : 0) + V[i];
	rep(c, C) {
		int b, h;
		scanf("%d%d", &b, &h);
		if(N - lv > h) puts("-1");
		else {
			int cnt = (int)(lower_bound(all(V), b) - V.begin());
			cnt = max(cnt, N - h);
			printf("%lld\n", (ll)(N - cnt) * b + (cnt ? SV[cnt-1] : 0));
		}
	}
	return 0;
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d%d", &N, &M, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
construction.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |   scanf("%d%d", &b, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17640 KB Output is correct
2 Correct 334 ms 26776 KB Output is correct
3 Correct 344 ms 26928 KB Output is correct
4 Correct 388 ms 35916 KB Output is correct
5 Correct 362 ms 32176 KB Output is correct
6 Correct 346 ms 30756 KB Output is correct
7 Correct 275 ms 39044 KB Output is correct
8 Correct 266 ms 33876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17640 KB Output is correct
2 Correct 334 ms 26776 KB Output is correct
3 Correct 344 ms 26928 KB Output is correct
4 Correct 388 ms 35916 KB Output is correct
5 Correct 362 ms 32176 KB Output is correct
6 Correct 346 ms 30756 KB Output is correct
7 Correct 275 ms 39044 KB Output is correct
8 Correct 266 ms 33876 KB Output is correct
9 Correct 1459 ms 58604 KB Output is correct
10 Correct 1442 ms 58868 KB Output is correct
11 Correct 1446 ms 58744 KB Output is correct
12 Correct 1446 ms 58764 KB Output is correct
13 Correct 926 ms 65816 KB Output is correct
14 Correct 358 ms 32180 KB Output is correct
15 Correct 1481 ms 58876 KB Output is correct
16 Correct 698 ms 72100 KB Output is correct
17 Correct 677 ms 72004 KB Output is correct
18 Correct 835 ms 69468 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17640 KB Output is correct
2 Correct 334 ms 26776 KB Output is correct
3 Correct 344 ms 26928 KB Output is correct
4 Correct 388 ms 35916 KB Output is correct
5 Correct 362 ms 32176 KB Output is correct
6 Correct 346 ms 30756 KB Output is correct
7 Correct 275 ms 39044 KB Output is correct
8 Correct 266 ms 33876 KB Output is correct
9 Correct 641 ms 46500 KB Output is correct
10 Correct 626 ms 43204 KB Output is correct
11 Correct 587 ms 42464 KB Output is correct
12 Correct 637 ms 40776 KB Output is correct
13 Correct 508 ms 38856 KB Output is correct
14 Correct 668 ms 45220 KB Output is correct
15 Correct 659 ms 45684 KB Output is correct
16 Correct 624 ms 44940 KB Output is correct
17 Correct 525 ms 44296 KB Output is correct
18 Correct 558 ms 42264 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 17640 KB Output is correct
2 Correct 334 ms 26776 KB Output is correct
3 Correct 344 ms 26928 KB Output is correct
4 Correct 388 ms 35916 KB Output is correct
5 Correct 362 ms 32176 KB Output is correct
6 Correct 346 ms 30756 KB Output is correct
7 Correct 275 ms 39044 KB Output is correct
8 Correct 266 ms 33876 KB Output is correct
9 Correct 1459 ms 58604 KB Output is correct
10 Correct 1442 ms 58868 KB Output is correct
11 Correct 1446 ms 58744 KB Output is correct
12 Correct 1446 ms 58764 KB Output is correct
13 Correct 926 ms 65816 KB Output is correct
14 Correct 358 ms 32180 KB Output is correct
15 Correct 1481 ms 58876 KB Output is correct
16 Correct 698 ms 72100 KB Output is correct
17 Correct 677 ms 72004 KB Output is correct
18 Correct 835 ms 69468 KB Output is correct
19 Correct 641 ms 46500 KB Output is correct
20 Correct 626 ms 43204 KB Output is correct
21 Correct 587 ms 42464 KB Output is correct
22 Correct 637 ms 40776 KB Output is correct
23 Correct 508 ms 38856 KB Output is correct
24 Correct 668 ms 45220 KB Output is correct
25 Correct 659 ms 45684 KB Output is correct
26 Correct 624 ms 44940 KB Output is correct
27 Correct 525 ms 44296 KB Output is correct
28 Correct 558 ms 42264 KB Output is correct
29 Correct 1680 ms 58956 KB Output is correct
30 Correct 999 ms 47288 KB Output is correct
31 Correct 1594 ms 58736 KB Output is correct
32 Correct 518 ms 39224 KB Output is correct
33 Correct 1619 ms 59028 KB Output is correct
34 Correct 565 ms 36092 KB Output is correct
35 Correct 1476 ms 56988 KB Output is correct
36 Correct 1690 ms 58872 KB Output is correct
37 Correct 926 ms 83768 KB Output is correct
38 Correct 1078 ms 69540 KB Output is correct
39 Correct 589 ms 42736 KB Output is correct