Submission #205576

#TimeUsernameProblemLanguageResultExecution timeMemory
205576jh05013절취선 (JOI14_ho_t5)C++17
50 / 100
215 ms10756 KiB
#include <bits/stdc++.h> #define sz(X) (int)((X).size()) #define entire(X) X.begin(),X.end() using namespace std; typedef long long ll; void OJize(){cin.tie(NULL);ios_base::sync_with_stdio(false);} template <class T1, class T2>ostream&operator<<(ostream &os,pair<T1,T2>const&x){os<<'('<<x.first<<", "<<x.second<<')';return os;} template <class Ch, class Tr, class Container>basic_ostream<Ch,Tr>&operator<<(basic_ostream<Ch,Tr>&os,Container const&x){for(auto&y:x)os<<y<<" ";return os;} template <typename T> struct Compress{ int n; vector<T> arr; void add(T x){arr.push_back(x); n++;} void init(){sort(entire(arr)), arr.erase(unique(entire(arr)), arr.end()), n=arr.size();} int lb(T x){return lower_bound(entire(arr), x) - arr.begin();} }; struct DisjointSet{ vector<int> par; DisjointSet(int n): par(n) {iota(entire(par), 0);} void un(int x, int y){par[fd(x)] = fd(y);} // yr becomes parent int fd(int x){return par[x]!=x? (par[x]=fd(par[x])):x;} }; template <typename T> struct Fenwick{ int n; vector<T> arr; Fenwick(int N): n{N}, arr(N) {} void add(int i, T val){ while(i < n) arr[i]+= val, i |= i+1; } T getsum(int i){ T res = 0; while(i >= 0) res+= arr[i], i = (i&(i+1))-1; return res; } T intersum(int i, int j){ if(j < i) return 0; return i? (getsum(j) - getsum(i-1)) : getsum(j); } }; int main(){OJize(); int w,h,n; cin>>w>>h>>n; vector<tuple<int,int,int,int,int>> ev; // y, type, l, r, idx Compress<int> C; C.add(0), C.add(w); // type 1 = vertical start (uses l=r) // type 2 = horizontal (uses l, r) // type 3 = vertical end (uses l=r) for(int i=0; i<n; i++){ int xa,ya,xb,yb; cin>>xa>>ya>>xb>>yb; C.add(xa), C.add(xb); if(xa == xb){ ev.push_back({ya, 1, xa, xb, i}); ev.push_back({yb, 3, xa, xb, i}); } else ev.push_back({ya, 2, xa, xb, i}); } ev.push_back({0,2,0,w,n}), ev.push_back({h,2,0,w,n+1}); ev.push_back({0,1,0,0,n+2}), ev.push_back({0,1,w,w,n+3}); ev.push_back({h,3,0,0,n+2}), ev.push_back({h,3,w,w,n+3}); C.init(), sort(entire(ev)); Fenwick<int> F(sz(C.arr)); // count V and E ll V=0, E=0, COMP=0; for(auto [y,ty,x1,x2,_]: ev){ x1 = C.lb(x1), x2 = C.lb(x2); if(ty == 1) F.add(x1, 1), V++; else if(ty == 2){ ll ic = F.intersum(x1, x2); V+= ic+2, E+= 2*ic+1; } else if(ty == 3) F.add(x1, -1), V++, E++; } // count COMP DisjointSet DS(n+4); COMP = 1; map<int,int> vert; vert[w+1] = -1; for(auto [y,ty,x1,x2,idx]: ev){ x1 = C.lb(x1), x2 = C.lb(x2); if(V > 2000000) break; // subtask 4 if(ty == 1){ vert[x1] = idx; } else if(ty == 2){ auto it = vert.lower_bound(x1); for(; it->first<=x2; it++) DS.un(idx, it->second); } else if(ty == 3){ vert.erase(x1); } } if(V <= 2000000){ COMP = 0; for(int i=0; i<sz(DS.par); i++) COMP+= DS.fd(i) == i; } cout << E-V+COMP; }

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:68:27: warning: unused variable 'y' [-Wunused-variable]
     for(auto [y,ty,x1,x2,_]: ev){
                           ^
2014_ho_t5.cpp:68:27: warning: unused variable '_' [-Wunused-variable]
2014_ho_t5.cpp:82:29: warning: unused variable 'y' [-Wunused-variable]
     for(auto [y,ty,x1,x2,idx]: ev){
                             ^
#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...