Submission #55208

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
55208	2018-07-06T10:33:24 Z	노영훈(#1526)	None (JOI14_ho_t5)	C++11	Compilation error	0 ms	0 KB

2014_ho_t5

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9, XMX=200010;

int w, h, n;

struct line {
    int x1, y1, x2, y2;
};
vector<line> L;

struct node {
    ll sum; int l, r;
} tree[XMX*20];
int now=0;

int root0[XMX];
int rootx[XMX];

int init(int v, int s, int e, int y, int val){
    if(y<s || e<y) return v;
    node &nd=tree[++now];
    nd=tree[v]; v=now;
    nd.sum+=val;
    if(s!=e){
        nd.l=init(nd.l, s, (s+e)/2, y, val);
        nd.r=init(nd.r, (s+e)/2+1, e, y, val);
    }
    return v;
}


ll sum(int v, int s, int e, int l, int r){
    if(e<l || r<s) return 0;
    node &nd=tree[v]; // 2-1
    if(l<=s && e<=r) return nd.sum;
    return sum(nd.l, s, (s+e)/2, l, r) + sum(nd.r, (s+e)/2+1, e, l, r);
}


ll vcnt=0, ecnt=0;


bool hit(line a, line b){
    if(a.y1==a.y2) swap(a,b);
    if(a.y1==a.y2) return false;
    if(b.x1==b.x2) return false;
    return (b.x1<=a.x1 && a.x1<=b.x2) && (a.y1<=b.y1 && b.y1<=a.y2);
}

int U[MX];

int find(int x){ return x==U[x] ? x : U[x]=find(U[x]); }
void unite(int x, int y){
    if(find(x)==find(y)) return;
    U[U[y]]=U[x];
}


map<int, int> Seg[4*XMX];

void put(int v, int s, int e, int y, int val){
    if(y<s || e<y) return;
    // cout<<"PUT: "<<y<<' '<<val<<'\n';
    Seg[v][val]++;
    if(s!=e){
        put(v*2,s,(s+e)/2,y,val);
        put(v*2+1,(s+e)/2+1,e,y,val);
    }
}
void pop(int v, int s, int e, int y, int val){
    if(y<s || e<y) return;
    // cout<<"POP: "<<y<<' '<<val<<'\n';
    Seg[v][val]--;
    if(Seg[v][val]==0) Seg[v].erase(val);
    if(s!=e){
        pop(v*2,s,(s+e)/2,y,val);
        pop(v*2+1,(s+e)/2+1,e,y,val);
    }
}

void get(int v, int s, int e, int l, int r, set<int> &res){
    if(e<l || r<s) return;
    if(l<=s && e<=r){
        for(pii p:Seg[v]) res.insert(p.first);
        return;
    }
    if(s!=e){
        get(v*2,s,(s+e)/2,l,r,res);
        get(v*2+1,(s+e)/2+1,e,l,r,res);
    }
}


vector<int> H[XMX];
vector<int> V;
int components(){
    int sz=L.size();
    for(int i=0; i<sz; i++) U[i]=i;
    for(int i=0; i<sz; i++){
        line &l=L[i];
        if(l.x1==l.x2){
            V.push_back(i);
            continue;
        }
        H[l.x1].push_back(i+1);
        H[l.x2+1].push_back(-i-1);
    }
    sort(V.begin(), V.end(), [](int a, int b){
        return L[a].x1<L[b].x1;
    });
    int x=0;
    for(int i:V){
        line &l=L[i];
        while(x<l.x1){
            x++;
            for(int idx:H[x]){
                if(idx>0) put(1,1,h,L[idx-1].y1,idx-1);
                else pop(1,1,h,L[-idx-1].y1,-idx-1);
            }
        }
        set<int> now;
        get(1,1,h,l.y1, l.y2, now);
        // cout<<l.x1<<' '<<l.y1<<' '<<l.x2<<' '<<l.y2<<": \n";
        for(int x:now) unite(i, x);
        // for(int x:now) cout<<L[x].x1<<' '<<L[x].y1<<' '<<L[x].x2<<' '<<L[x].y2<<'\n';
    }
    set<int> cnt;
    for(int i=0; i<sz; i++) cnt.insert(find(i));
    // cout<<cnt.size()<<'\n';
    return cnt.size();
}



vector<pii> P;
vector<line> H[XMX];

int fenwick[XMX];
void upt(int y, int val){
    for(; 0<y; y-=y&(-y)) fenwick[y]+=val;
}
void upt(int l, int r, int val){
    upt(r,val); upt(l-1,-val);
}
int val(int y){
    int res=0;
    for(; y<=w; y+=y&(-y)) res+=fenwick[y];
    return res;
}
void normalize(){
    // cout<<"NORM\n";
    for(line &l:L){
        if(l.y1==l.y2){
            P.push_back({l.x1,l.y1});
            P.push_back({l.x2,l.y2});
        }
        else{
            H[l.x1].push_back(l);
        }
    }
    sort(P.begin(), P.end());
    for(int i=0, x=0; i<(int)P.size(); i++){
        if(x!=P[i].first){
            for(line &l:H[x]){
                upt(l.y1, l.y2, -1);
            }
            x=P[i].first;
            for(line &l:H[x]){
                upt(l.y1, l.y2, 1);
            }
        }
        int now=val(P[i].second);
        if(now==0) vcnt++;
        if(now!=0) ecnt--;
    }
    // cout<<ecnt<<' '<<vcnt<<'\n';
}

void solve(){
    // cout<<"SOLVE!\n";
    for(line &l:L){
        if(l.y1==l.y2) continue;
        int rt=rootx[l.x1];
        int hit=sum(rt, 1, h, l.y1, l.y2);
        ecnt+=hit;
        int nowv=hit+2-sum(rt, 1, h, l.y1, l.y1)-sum(rt, 1, h, l.y2, l.y2);
        vcnt+=nowv;
        ecnt+=nowv-1;
        // cout<<l.x1<<' '<<l.y1<<" ~ "<<l.y2<<": "<<hit<<'\n';
        // cout<<ecnt<<' '<<vcnt<<'\n';
    }
    // cout<<ecnt<<' '<<vcnt<<'\n';
}

map<int, int> diff[XMX];
void put_horz(){
    for(line &l:L){
        if(l.x1==l.x2) continue;
        ecnt++;
        diff[l.x1][l.y1]++;
        diff[l.x2+1][l.y2]--;
    }
    int idx=0;
    for(int x=1; x<=w; x++){
        for(pii p:diff[x]){
            idx++;
            root0[idx]=init(root0[idx-1], 1, h, p.first, p.second);
        }
        rootx[x]=root0[idx];
    }
    // for(int i=1; i<=w; i++) cout<<rootx[i]<<' ';
    // cout<<'\n';
    // cout<<ecnt<<' '<<vcnt<<'\n';
}


int find(int x, vector<int> &X){
    return lower_bound(X.begin(), X.end(), x)-X.begin()+1;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>w>>h>>n;

    vector<int> X, Y;
    for(int i=1; i<=n; i++){
        int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2;
        L.push_back({x1,y1,x2,y2});
        X.push_back(x1); X.push_back(x2);
        Y.push_back(y1); Y.push_back(y2);
    }
    L.push_back({0,0,w,0}); L.push_back({0,h,w,h});
    L.push_back({0,0,0,h}); L.push_back({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());
    X.resize(unique(X.begin(), X.end())-X.begin());
    sort(Y.begin(), Y.end());
    Y.resize(unique(Y.begin(), Y.end())-Y.begin());


    w=find(w,X); h=find(h,Y);
    for(line &l:L){
        l={find(l.x1,X), find(l.y1,Y), find(l.x2,X), find(l.y2,Y)};
    }

    put_horz();
    solve();
    normalize();
    ll ans=ecnt-vcnt+components();
    cout<<ans;

    return 0;
}

Compilation message

2014_ho_t5.cpp:139:19: error: conflicting declaration 'std::vector<line> H [200010]'
 vector<line> H[XMX];
                   ^
2014_ho_t5.cpp:97:13: note: previous declaration as 'std::vector<int> H [200010]'
 vector<int> H[XMX];
             ^
2014_ho_t5.cpp: In function 'void normalize()':
2014_ho_t5.cpp:161:32: error: no matching function for call to 'std::vector<int>::push_back(line&)'
             H[l.x1].push_back(l);
                                ^
In file included from /usr/include/c++/7/vector:64:0,
                 from /usr/include/c++/7/queue:61,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:86,
                 from 2014_ho_t5.cpp:1:
/usr/include/c++/7/bits/stl_vector.h:939:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       push_back(const value_type& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:939:7: note:   no known conversion for argument 1 from 'line' to 'const value_type& {aka const int&}'
/usr/include/c++/7/bits/stl_vector.h:953:7: note: candidate: void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = int; _Alloc = std::allocator<int>; std::vector<_Tp, _Alloc>::value_type = int]
       push_back(value_type&& __x)
       ^~~~~~~~~
/usr/include/c++/7/bits/stl_vector.h:953:7: note:   no known conversion for argument 1 from 'line' to 'std::vector<int>::value_type&& {aka int&&}'
2014_ho_t5.cpp:167:28: error: invalid initialization of reference of type 'line&' from expression of type 'int'
             for(line &l:H[x]){
                            ^
2014_ho_t5.cpp:171:28: error: invalid initialization of reference of type 'line&' from expression of type 'int'
             for(line &l:H[x]){
                            ^