Submission #229982

#	Time	Username	Problem	Language	Result	Execution time	Memory
229982		dennisstar	절취선 (JOI14_ho_t5)	C++17	100 / 100	1988 ms	148284 KiB

2014_ho_t5

#include <bits/stdc++.h>
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define all(V) (V).begin(), (V).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MX = 7<<15;

struct line {
	int x1, x2, y, t;
	line (int A, int B, int C, int D) {
		if (B==D) x1=A, x2=C, y=B, t=0;
		else x1=B, x2=D, y=A, t=1;
	}
};

int W, H, N;
vector<line> L;

struct seg {
	set<pii> st[1<<19];
	int l, r, y, x1;
	pii v;
	void U(int i=1, int s=0, int e=MX) {
		if (e<l||r<s) return ;
		if (l<=s&&e<=r) { st[i].em(v); return ; }
		int m=(s+e)/2;
		U(i*2, s, m); U(i*2+1, m+1, e);
	}
	void upd(int L, int R, pii V) {
		l=L, r=R, v=V;
		if (l>r) swap(l, r);
		U();
	}
	pii G(int i=1, int s=0, int e=MX) {
		auto k=st[i].lower_bound(pii(x1, -1));
		pii r=(k==st[i].end()?pii(MX+5, -1):*k);
		if (s==e) return r;
		int m=(s+e)/2;
		if (y<=m) return min(r, G(i*2, s, m));
		return min(r, G(i*2+1, m+1, e));
	}
	pii get(int Y, int X1) {
		y=Y, x1=X1;
		return G();
	}
	void E(int i=1, int s=0, int e=MX) {
		if (e<l||r<s) return ;
		if (l<=s&&e<=r) { st[i].erase(v); return ; }
		int m=(s+e)/2;
		E(i*2, s, m); E(i*2+1, m+1, e);
	}
	void er(int L, int R, pii V) {
		l=L, r=R, v=V;
		if (l>r) swap(l, r);
		E();
	}
}S[2];

int Find(vector<int> &V, int c) { return lower_bound(all(V), c)-V.begin(); }

vector<int> C1;
void dfs(int n) {
	S[L[n].t].er(L[n].x1, L[n].x2, pii(L[n].y, n));
	C1[n]=1;
	while (1) {
		auto k=S[L[n].t^1].get(L[n].y, L[n].x1);
		if (k.fi<=L[n].x2) dfs(k.se);
		else break;
	}
}

ll Component() {
	C1.resize(N);
	for (int i=0; i<N; i++) S[L[i].t].upd(L[i].x1, L[i].x2, pii(L[i].y, i));
	ll r=0;
	for (int i=0; i<N; i++) if (!C1[i]) r++, dfs(i);
	return r;
}

struct FW {
	int F[1<<18];
	void upd(int t, int v) { t++; while (t<(1<<18)) F[t]+=v, t+=t&-t; }
	int get(int t) { int r=0; while (t) r+=F[t], t-=t&-t; return r; }
	int get(int l, int r) {
		if (l>r) return 0;
		return get(r+1)-get(l);
	}
}T[2];

ll VE() {
	ll V=0, VV=0, E=0;
	vector<vector<int>> V1(MX), V2(MX);
	vector<line> G[2];
	for (auto &i:L) G[i.t].eb(i);
	for (auto &i:G[1]) V1[i.x2].eb(i.y);
	for (auto &i:G[0]) V2[i.x2].eb(i.y);

	int s=0, e=0;
	sort(all(G[0]), [](line &l1, line &l2) { return l1.y<l2.y; });
	sort(all(G[1]), [](line &l1, line &l2) { return l1.x1<l2.x1; });
	for (auto &i:G[0]) {
		for (; s<G[1].size()&&G[1][s].x1<=i.y; s++) T[0].upd(G[1][s].y, 1);
		for (; e<i.y; e++) for (auto &j:V1[e]) T[0].upd(j, -1);
		int r1=T[0].get(i.x1, i.x1), r2=T[0].get(i.x1+1, i.x2-1), r3=T[0].get(i.x2, i.x2);
		E+=r2+1;
		VV+=r1+r2+r3;
		V+=2-r1-r3;
	}

	s=0, e=0;
	sort(all(G[1]), [](line &l1, line &l2) { return l1.y<l2.y; });
	sort(all(G[0]), [](line &l1, line &l2) { return l1.x1<l2.x1; });
	for (auto &i:G[1]) {
		for (; s<G[0].size()&&G[0][s].x1<=i.y; s++) T[1].upd(G[0][s].y, 1);
		for (; e<i.y; e++) for (auto &j:V2[e]) T[1].upd(j, -1);
		int r1=T[1].get(i.x1, i.x1), r2=T[1].get(i.x1+1, i.x2-1), r3=T[1].get(i.x2, i.x2);
		E+=r2+1;
		VV+=r1+r2+r3;
		V+=2-r1-r3;
	}

	return VV/2+V-E;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	cin>>H>>W>>N;

	vector<int> cx, cy;
	cx.eb(0), cx.eb(H);
	cy.eb(0), cy.eb(W);
	L.eb(0, 0, 0, W);
	L.eb(H, 0, H, W);
	L.eb(0, 0, H, 0);
	L.eb(0, W, H, W);

	for (int i=0, a, b, c, d; i<N; i++)
		cin>>a>>b>>c>>d,
		L.eb(a, b, c, d),
		cx.eb(a), cx.eb(c),
		cy.eb(b), cy.eb(d);

	sort(all(cx)); sort(all(cy));
	H=Find(cx, H); W=Find(cy, W);
	for (auto &i:L) {
		if (i.t==0) i.x1=Find(cx, i.x1), i.x2=Find(cx, i.x2), i.y=Find(cy, i.y);
		if (i.t==1) i.x1=Find(cy, i.x1), i.x2=Find(cy, i.x2), i.y=Find(cx, i.y);
	}

	N+=4;
	cout<<Component()-VE()<<'\n';
	return 0;
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'll VE()':
2014_ho_t5.cpp:107:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; s<G[1].size()&&G[1][s].x1<=i.y; s++) T[0].upd(G[1][s].y, 1);
          ~^~~~~~~~~~~~
2014_ho_t5.cpp:119:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (; s<G[0].size()&&G[0][s].x1<=i.y; s++) T[1].upd(G[0][s].y, 1);
          ~^~~~~~~~~~~~

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