Submission #12970

#	Time	Username	Problem	Language	Result	Execution time	Memory
12970		ainta	도로 건설 사업 (JOI13_construction)	C++98	100 / 100	1680 ms	60516 KiB

construction

#include<stdio.h>
#include<algorithm>
#define SZ 1048576
using namespace std;
int n, m, Q, D[201000], par[201000];
long long SS[201000];
struct Rectangle{
	int x1, x2, y1, y2;
}Rect[201000];
struct Seg{
	int x, y1, y2, ck;
	bool operator<(const Seg &p)const{
		return x < p.x;
	}
}S[401000];
struct point{
	int x, y, num;
	bool operator<(const point &p)const{
		return x != p.x ? x < p.x : y < p.y;
	}
}w[201000], Tw[201000];
struct order{
	int y, num;
	bool operator<(const order &p)const{
		return y < p.y;
	}
}Y[601000];
struct Edge{
	int a, b, d;
	bool operator<(const Edge &p)const{
		return d < p.d;
	}
}E[401000];
int cnt;

struct SegTree{
	long long S;
	int K;
}IT[SZ+SZ+2];

void Add2(int nd, int b, int e, int x){
	IT[nd].K += x;
	IT[nd].S += (long long)(e - b + 1)*x;
	return;
}
void spread(int nd, int b, int m, int e){
	if (!IT[nd].K)return;
	Add2(nd * 2, b, m, IT[nd].K);
	Add2(nd * 2 + 1, m + 1, e, IT[nd].K);
	IT[nd].K = 0;
}

void Add(int nd, int b, int e, int s, int l, int x){
	if (b == s && e == l){
		Add2(nd, b, e, x);
		return;
	}
	int m = (b + e) >> 1;
	spread(nd, b, m, e);
	if (s <= m)Add(nd * 2, b, m, s, min(m, l), x);
	if (l > m)Add(nd * 2 + 1, m + 1, e, max(m + 1, s), l, x);
	IT[nd].S = IT[nd * 2].S + IT[nd * 2 + 1].S;
}
long long Sum(int nd, int b, int e, int s, int l){
	long long r = 0;
	if (b == s && e == l)return IT[nd].S;
	int m = (b + e) >> 1;
	spread(nd, b, m, e);
	if (s <= m)r += Sum(nd * 2, b, m, s, min(m, l));
	if (l > m)r += Sum(nd * 2 + 1, m + 1, e, max(m + 1, s), l);
	return r;
}
void Do(){
	int i, t = 0, pv;
	for (i = 1; i <= n; i++){
		Y[i].y = w[i].y, Y[i].num = i;
		Tw[i].x = w[i].x, Tw[i].num = i;
	}
	for (i = 1; i <= m; i++){
		Y[i + n].y = Rect[i].y1, Y[i + n].num = i + n;
		Y[i + n + m].y = Rect[i].y2, Y[i + n + m].num = i + n + m;
	}
	sort(Y + 1, Y + n + m + m + 1);
	for (i = 1; i <= n + m + m; i++){
		if (i == 1 || Y[i].y != Y[t].y)t = i;
		if (Y[i].num <= n)Tw[Y[i].num].y = t;
		else if (Y[i].num <= n + m)Rect[Y[i].num - n].y1 = t;
		else Rect[Y[i].num - n - m].y2 = t;
	}
	for (i = 1; i <= m; i++){
		S[i].y1 = S[i + m].y1 = Rect[i].y1, S[i].y2 = S[i + m].y2 = Rect[i].y2;
		S[i].x = Rect[i].x1, S[i + m].x = Rect[i].x2 + 1;
		S[i].ck = 1, S[i + m].ck = -1;
	}
	sort(Tw, Tw + n + 1);
	sort(S + 1, S + m + m + 1);
	pv = 1;
	for (i = 1; i <= m + m + 1; i++){
		while (pv + 1 <= n && (i == m + m + 1 || Tw[pv + 1].x < S[i].x)){
			if (Tw[pv].x == Tw[pv + 1].x){
				if (!Sum(1, 1, SZ, Tw[pv].y, Tw[pv + 1].y)){
					E[cnt].a = Tw[pv].num, E[cnt].b = Tw[pv + 1].num, E[cnt].d = Y[Tw[pv + 1].y].y - Y[Tw[pv].y].y;
					cnt++;
				}
			}
			pv++;
		}
		if (i == m + m + 1)break;
		Add(1, 1, SZ, S[i].y1, S[i].y2, S[i].ck);
	}
	for (i = 1; i <= m; i++){
		Rect[i].y1 = Y[Rect[i].y1].y;
		Rect[i].y2 = Y[Rect[i].y2].y;
	}
}
int find(int a){
	return a == par[a] ? a : par[a] = find(par[a]);
}
int main(){
	int i, c = 0, a, b, be, ed, mid, r;
	scanf("%d%d%d", &n, &m, &Q);
	for (i = 1; i <= n; i++){
		scanf("%d%d", &w[i].x, &w[i].y);
	}
	for (i = 1; i <= m; i++){
		scanf("%d%d%d%d", &Rect[i].x1, &Rect[i].y1, &Rect[i].x2, &Rect[i].y2);
	}
	Do();
	for (i = 1; i <= n; i++){
		swap(w[i].x, w[i].y);
	}
	for (i = 1; i <= m; i++){
		swap(Rect[i].x1, Rect[i].y1);
		swap(Rect[i].x2, Rect[i].y2);
	}
	Do();
	sort(E, E + cnt);
	for (i = 1; i <= n; i++)par[i] = i;
	for (i = 0; i < cnt; i++){
		a = find(E[i].a), b = find(E[i].b);
		if (a != b){
			par[a] = b;
			D[++c] = E[i].d;
			SS[c] = SS[c - 1] + D[c];
		}
	}
	long long Res;
	while (Q--){
		scanf("%d%d", &a, &b);
		if (b + c < n){
			printf("-1\n");
			continue;
		}
		be = 1, ed = c, r = 0;
		while (be <= ed){
			mid = (be + ed) >> 1;
			if (D[mid] <= a){
				r = mid; be = mid + 1;
			}
			else ed = mid - 1;
		}
		if (b < n - r)Res = (long long)b*a + SS[n - b];
		else Res = (long long)(n - r)*a + SS[r];
		printf("%lld\n", Res);
	}
	return 0;
}

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