Submission #287074

#	Time	Username	Problem	Language	Result	Execution time	Memory
287074		cki86201	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	1690 ms	83768 KiB

construction

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30