| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 229976 |
2020-05-07T12:43:14 Z |
dennisstar |
None (JOI14_ho_t5) |
C++17 |
|
1948 ms |
166248 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;
}
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);
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
60408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
60408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
60664 KB |
Output is correct |
| 2 |
Correct |
44 ms |
60792 KB |
Output is correct |
| 3 |
Correct |
42 ms |
60664 KB |
Output is correct |
| 4 |
Correct |
46 ms |
60920 KB |
Output is correct |
| 5 |
Incorrect |
95 ms |
66168 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
40 ms |
60416 KB |
Output is correct |
| 2 |
Correct |
48 ms |
61056 KB |
Output is correct |
| 3 |
Correct |
118 ms |
62752 KB |
Output is correct |
| 4 |
Correct |
41 ms |
60408 KB |
Output is correct |
| 5 |
Correct |
43 ms |
61056 KB |
Output is correct |
| 6 |
Correct |
1948 ms |
141800 KB |
Output is correct |
| 7 |
Correct |
76 ms |
64760 KB |
Output is correct |
| 8 |
Correct |
484 ms |
100200 KB |
Output is correct |
| 9 |
Correct |
1133 ms |
164200 KB |
Output is correct |
| 10 |
Correct |
1129 ms |
166248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
40 ms |
60408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
