Submission #230240

#	Time	Username	Problem	Language	Result	Execution time	Memory
230240		onjo0127	절취선 (JOI14_ho_t5)	C++11	100 / 100	1166 ms	12132 KiB

2014_ho_t5

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
const int _N = 100009;

struct line {
	int p, l, r;
};

long long ans;
int W, H, N, A[_N], B[_N], C[_N], D[_N], pa[_N], lc;
set<pii> S;
line L[_N];

int getx(vector<int> &S, int x) { return lower_bound(S.begin(), S.end(), x) - S.begin() + 1; }

int root(int x) {
	if(pa[x] == x) return x;
	return pa[x] = root(pa[x]);
}
void merg(int u, int v) {
	u = root(u); v = root(v);
	if(u != v) pa[u] = v;
}

void dnc_y(int s, int e, vector<int> &VL, vector<int> &HL) {
	if(VL.empty() || HL.empty()) return;
	vector<int> MV, NV, LH, RH;
	int m = s+e >> 1;
	for(auto& it: VL) {
		if(L[it].r < s || e < L[it].l) continue;
		if(L[it].l <= s && e <= L[it].r) MV.push_back(it);
		else NV.push_back(it);
	}
	for(auto& it: HL) {
		if(L[it].p <= m) LH.push_back(it);
		else RH.push_back(it);
	}
	if(s != e) {
		dnc_y(s, m, NV, LH);
		dnc_y(m+1, e, NV, RH);
	}
	if(MV.size()) {
		ans += (ll)MV.size() * (ll)HL.size();
		for(auto& it: MV) merg(it, HL[0]);
		for(auto& it: HL) merg(it, HL[0]);
	}
}

void dnc_x(int s, int e, vector<int> &VL, vector<int> &HL) {
	if(VL.empty() || HL.empty()) return;
	vector<int> LV, RV, NH, MH;
	int m = s+e >> 1;
	for(auto& it: VL) {
		if(L[it].p <= m) LV.push_back(it);
		else RV.push_back(it);
	}
	for(auto& it: HL) {
		if(L[it].r < s || e < L[it].l) continue;
		if(L[it].l <= s && e <= L[it].r) MH.push_back(it);
		else NH.push_back(it);
	}
	if(s != e) {
		dnc_x(s, m, LV, NH);
		dnc_x(m+1, e, RV, NH);
	}
	dnc_y(1, H, VL, MH);
}

int main() {
	vector<int> XS, YS;
	scanf("%d%d%d",&W,&H,&N);
	XS.push_back(0); XS.push_back(W);
	YS.push_back(0); YS.push_back(H);
	for(int i=0; i<N; i++) {
		scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
		XS.push_back(A[i]); XS.push_back(C[i]);
		YS.push_back(B[i]); YS.push_back(D[i]);
	}
	sort(XS.begin(), XS.end()); XS.resize(unique(XS.begin(), XS.end()) - XS.begin());
	sort(YS.begin(), YS.end()); YS.resize(unique(YS.begin(), YS.end()) - YS.begin());
	W = getx(XS, W); H = getx(YS, H);
	for(int i=0; i<N; i++) {
		A[i] = getx(XS, A[i]);
		B[i] = getx(YS, B[i]);
		C[i] = getx(XS, C[i]);
		D[i] = getx(YS, D[i]);
	}
	vector<int> VL, HL;
	L[++lc] = {1, 1, H}; VL.push_back(lc);
	L[++lc] = {W, 1, H}; VL.push_back(lc);
	L[++lc] = {1, 1, W}; HL.push_back(lc);
	L[++lc] = {H, 1, W}; HL.push_back(lc);
	for(int i=0; i<N; i++) {
		if(A[i] == C[i]) {
			L[++lc] = {A[i], B[i], D[i]};
			VL.push_back(lc);
		}
		if(B[i] == D[i]) {
			L[++lc] = {B[i], A[i], C[i]};
			HL.push_back(lc);
		}
	}
	for(int i=1; i<=lc; i++) pa[i] = i;
	ans = -N-4;
	dnc_x(1, W, VL, HL);
	for(int i=1; i<=lc; i++) if(root(i) == i) ++ans;
	ans += S.size();
	printf("%lld", ans);
	return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'void dnc_y(int, int, std::vector<int>&, std::vector<int>&)':
2014_ho_t5.cpp:30:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
2014_ho_t5.cpp: In function 'void dnc_x(int, int, std::vector<int>&, std::vector<int>&)':
2014_ho_t5.cpp:54:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:73:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&W,&H,&N);
  ~~~~~^~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50