Submission #95768

#TimeUsernameProblemLanguageResultExecution timeMemory
95768easrui절취선 (JOI14_ho_t5)C++14
0 / 100
278 ms12268 KiB
#include <bits/stdc++.h> #define sz first #define col second using namespace std; const int MN = 1e5+9; typedef pair<int,int> pii; struct line{ int A,B,C,D; line(){}; line(int a, int b, int c, int d){ A = a, B = b , C = c, D = d; } } L[MN]; struct event{ int s,e,t,v; event(){}; event(int a, int b, int c, int d){ s = a, e = b, t = c, v = d; } bool operator < (const event &A) const{ if(t==A.t){ return A.v<v; } return t<A.t; } } E[2*MN]; int W,H,N,A,B,C,D,par[MN],cnt,comp,nume,inter; bool ch[MN]; pii T[MN]; vector<int> X,Y; bool cmp(event A, event B) { if(A.t==B.t) return B.v>A.v; return A.t<B.t; } int fnd(int a) { return par[a]==a ? a : par[a] = fnd(par[a]); } void join(int a, int b) { if(a==0 || b==0) return; a = fnd(a), b = fnd(b); if(a!=b) par[b] = a; } void upt(int x, int v, int s, int e, int pos) { if(x<s || x>e) return; int c = T[pos].col; if(c){ if(T[2*pos].sz) join(T[2*pos].col,c); if(T[2*pos+1].sz) join(T[2*pos+1].col,c); T[2*pos].col = c; T[2*pos+1].col = c; T[pos].col = 0; } if(s==e){ T[pos].sz += v; return; } int m = (s+e)/2; upt(x,v,s,m,2*pos); upt(x,v,m+1,e,2*pos+1); T[pos].sz = T[2*pos].sz + T[2*pos+1].sz; } int sum(int l, int r, int s, int e, int pos) { if(l>r) return 0; if(r<s || e<l) return 0; if(l<=s && e<=r) return T[pos].sz; int m = (s+e)/2; return sum(l,r,s,m,2*pos)+sum(l,r,m+1,e,2*pos+1); } void act(int l, int r, int s, int e, int pos) { if(r<s || l>e) return; int c = T[pos].col; if(c){ if(T[2*pos].sz) join(T[2*pos].col,c); if(T[2*pos+1].sz) join(T[2*pos+1].col,c); T[2*pos].col = c; T[2*pos+1].col = c; T[pos].col = 0; } if(l<=s && e<=r){ if(T[pos].sz) join(c,cnt); T[pos].col = cnt; return; } int m = (s+e)/2; act(l,r,s,m,2*pos); act(l,r,m+1,e,2*pos+1); } int main() { //freopen("input.txt","r",stdin); cin >> W >> H >> N; for(int i=0; i<N; i++){ cin >> A >> B >> C >> D; if(A>C) swap(A,C); if(B>D) swap(B,D); L[i] = line(A,B,C,D); X.push_back(A); X.push_back(C); Y.push_back(B); Y.push_back(D); } L[N] = line(0,0,0,H); L[N+1] = line(0,0,W,0); L[N+2] = line(0,H,W,H); L[N+3] = line(W,0,W,H); X.push_back(0); X.push_back(W); Y.push_back(0); Y.push_back(H); sort(X.begin(),X.end()); sort(Y.begin(),Y.end()); X.erase(unique(X.begin(),X.end()),X.end()); Y.erase(unique(Y.begin(),Y.end()),Y.end()); nume = N+4; for(int i=0; i<N+4; i++){ L[i].A = lower_bound(X.begin(),X.end(),L[i].A)-X.begin(); L[i].C = lower_bound(X.begin(),X.end(),L[i].C)-X.begin(); L[i].B = lower_bound(Y.begin(),Y.end(),L[i].B)-Y.begin(); L[i].D = lower_bound(Y.begin(),Y.end(),L[i].D)-Y.begin(); if(L[i].C!=L[i].A){ E[i] = event(L[i].B,L[i].D,L[i].A,1); E[nume++] = event(L[i].B,L[i].D,L[i].C,-1); } else E[i] = event(L[i].B,L[i].D,L[i].C,0); } sort(E,E+nume); for(int i=0; i<nume; i++){ if(E[i].v) upt(E[i].s,E[i].v,0,Y.size()-1,1); else{ cnt++; par[cnt] = cnt; act(E[i].s,E[i].e,0,Y.size()-1,1); inter += sum(E[i].s,E[i].e,0,Y.size()-1,1); } } for(int i=1; i<=cnt; i++) ch[fnd(i)] = true; for(int i=1; i<=cnt; i++) comp += ch[i]; cout << comp-N+inter-4; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...