oj.uz

Submission #229978

# Submission time Handle Problem Language Result Execution time Memory
229978 2020-05-07T12:49:19 Z dennisstar None (JOI14_ho_t5) C++17
20 / 100
 1914 ms 163804 KB 
#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 (A>C) swap(A, C);
		if (B>D) swap(B, 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;
		assert((r1==0||r1==1)&&(r3==0||r3==1));
	}

	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;
	}
	assert(VV%2==0);

	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)); cx.resize(unique(all(cx))-cx.begin());
	sort(all(cy)); cy.resize(unique(all(cy))-cy.begin());
	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);
	}

	cout<<Component()-VE()<<'\n';
	return 0;
}

Compilation message

2014_ho_t5.cpp: In function 'll VE()':
2014_ho_t5.cpp:109: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:122: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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 60416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 60416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 60668 KB Output is correct
2 Correct 42 ms 60792 KB Output is correct
3 Correct 41 ms 60664 KB Output is correct
4 Correct 43 ms 61056 KB Output is correct
5 Incorrect 106 ms 66144 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 60536 KB Output is correct
2 Correct 45 ms 61048 KB Output is correct
3 Correct 118 ms 62752 KB Output is correct
4 Correct 40 ms 60416 KB Output is correct
5 Correct 44 ms 61056 KB Output is correct
6 Correct 1914 ms 138728 KB Output is correct
7 Correct 67 ms 64760 KB Output is correct
8 Correct 465 ms 97768 KB Output is correct
9 Correct 1110 ms 161896 KB Output is correct
10 Correct 1188 ms 163804 KB Output is correct

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 60416 KB Output isn't correct
2 Halted 0 ms 0 KB -