| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230237 |
2020-05-09T09:35:11 Z |
onjo0127 |
None (JOI14_ho_t5) |
C++11 |
|
3000 ms |
9572 KB |
#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]);
for(auto& it: MV) for(auto& jt: HL) S.insert({it, jt});
}
}
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(B[i]);
YS.push_back(C[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] = {0, 0, H}; VL.push_back(lc);
L[++lc] = {W, 0, H}; VL.push_back(lc);
L[++lc] = {0, 0, W}; HL.push_back(lc);
L[++lc] = {H, 0, 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(auto& it: VL) for(auto& jt: HL) {
if(L[it].l <= L[jt].p && L[jt].p <= L[it].r && L[jt].l <= L[it].p && L[it].p <= L[jt].r) {
merg(it, jt);
++ans;
}
}
for(int i=1; i<=lc; i++) if(root(i) == i) ++ans;
ans += S.size();
printf("%lld", ans);
return 0;
}
//f = c-v+e
Compilation message
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:55:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = s+e >> 1;
~^~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:74: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:78: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
384 KB |
Output is correct |
| 11 |
Correct |
8 ms |
384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
384 KB |
Output is correct |
| 13 |
Correct |
8 ms |
384 KB |
Output is correct |
| 14 |
Correct |
6 ms |
384 KB |
Output is correct |
| 15 |
Correct |
6 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
384 KB |
Output is correct |
| 11 |
Correct |
8 ms |
384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
384 KB |
Output is correct |
| 13 |
Correct |
8 ms |
384 KB |
Output is correct |
| 14 |
Correct |
6 ms |
384 KB |
Output is correct |
| 15 |
Correct |
6 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
8 ms |
384 KB |
Output is correct |
| 22 |
Correct |
7 ms |
384 KB |
Output is correct |
| 23 |
Correct |
8 ms |
384 KB |
Output is correct |
| 24 |
Correct |
9 ms |
384 KB |
Output is correct |
| 25 |
Correct |
8 ms |
384 KB |
Output is correct |
| 26 |
Correct |
7 ms |
384 KB |
Output is correct |
| 27 |
Correct |
8 ms |
384 KB |
Output is correct |
| 28 |
Correct |
8 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
384 KB |
Output is correct |
| 2 |
Correct |
6 ms |
384 KB |
Output is correct |
| 3 |
Correct |
6 ms |
384 KB |
Output is correct |
| 4 |
Correct |
7 ms |
512 KB |
Output is correct |
| 5 |
Correct |
154 ms |
1280 KB |
Output is correct |
| 6 |
Execution timed out |
3089 ms |
5100 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
8 ms |
384 KB |
Output is correct |
| 3 |
Correct |
271 ms |
1284 KB |
Output is correct |
| 4 |
Correct |
4 ms |
384 KB |
Output is correct |
| 5 |
Correct |
8 ms |
384 KB |
Output is correct |
| 6 |
Execution timed out |
3087 ms |
9572 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
384 KB |
Output is correct |
| 2 |
Correct |
5 ms |
384 KB |
Output is correct |
| 3 |
Correct |
5 ms |
384 KB |
Output is correct |
| 4 |
Correct |
5 ms |
384 KB |
Output is correct |
| 5 |
Correct |
5 ms |
384 KB |
Output is correct |
| 6 |
Correct |
5 ms |
384 KB |
Output is correct |
| 7 |
Correct |
6 ms |
384 KB |
Output is correct |
| 8 |
Correct |
8 ms |
384 KB |
Output is correct |
| 9 |
Correct |
6 ms |
384 KB |
Output is correct |
| 10 |
Correct |
8 ms |
384 KB |
Output is correct |
| 11 |
Correct |
8 ms |
384 KB |
Output is correct |
| 12 |
Correct |
6 ms |
384 KB |
Output is correct |
| 13 |
Correct |
8 ms |
384 KB |
Output is correct |
| 14 |
Correct |
6 ms |
384 KB |
Output is correct |
| 15 |
Correct |
6 ms |
384 KB |
Output is correct |
| 16 |
Correct |
5 ms |
384 KB |
Output is correct |
| 17 |
Correct |
5 ms |
384 KB |
Output is correct |
| 18 |
Correct |
5 ms |
384 KB |
Output is correct |
| 19 |
Correct |
5 ms |
384 KB |
Output is correct |
| 20 |
Correct |
5 ms |
384 KB |
Output is correct |
| 21 |
Correct |
8 ms |
384 KB |
Output is correct |
| 22 |
Correct |
7 ms |
384 KB |
Output is correct |
| 23 |
Correct |
8 ms |
384 KB |
Output is correct |
| 24 |
Correct |
9 ms |
384 KB |
Output is correct |
| 25 |
Correct |
8 ms |
384 KB |
Output is correct |
| 26 |
Correct |
7 ms |
384 KB |
Output is correct |
| 27 |
Correct |
8 ms |
384 KB |
Output is correct |
| 28 |
Correct |
8 ms |
512 KB |
Output is correct |
| 29 |
Correct |
7 ms |
384 KB |
Output is correct |
| 30 |
Correct |
6 ms |
384 KB |
Output is correct |
| 31 |
Correct |
6 ms |
384 KB |
Output is correct |
| 32 |
Correct |
7 ms |
512 KB |
Output is correct |
| 33 |
Correct |
154 ms |
1280 KB |
Output is correct |
| 34 |
Execution timed out |
3089 ms |
5100 KB |
Time limit exceeded |
| 35 |
Halted |
0 ms |
0 KB |
- |
