Submission #204493

#	Time	Username	Problem	Language	Result	Execution time	Memory
204493		gs18115	절취선 (JOI14_ho_t5)	C++14	100 / 100	362 ms	24576 KiB

2014_ho_t5

#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
struct dsu
{
    int pa[100020];
    dsu(){}
    inline void init()
    {
        fill(pa,pa+100020,-1);
        return;
    }
    inline int par(int x)
    {
        if(pa[x]==-1)
            return x;
        return pa[x]=par(pa[x]);
    }
    inline void uni(int x,int y)
    {
        x=par(x);
        y=par(y);
        if(x==y)
            return;
        pa[x]=y;
        return;
    }
}uf;
struct seg
{
    int mx[800020];
    bool mg[800020];
    seg(){}
    inline void init()
    {
        fill(mx,mx+800020,-1);
        fill(mg,mg+800020,0);
        return;
    }
    inline void prop(int n)
    {
        if(mg[n])
        {
            mg[n*2]=mg[n*2+1]=1;
            if(mx[n*2]!=-1&&mx[n*2+1]!=-1)
                uf.uni(mx[n*2],mx[n*2+1]);
        }
        mg[n]=0;
        return;
    }
    inline void set(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            mx[n]=p;
            return;
        }
        prop(n);
        int m=(s+e)/2;
        if(x>m)
            set(n*2+1,m+1,e,x,p);
        else
            set(n*2,s,m,x,p);
        mx[n]=max(mx[n*2],mx[n*2+1]);
        return;
    }
    inline void mrg(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e||mx[n]==-1)
            return;
        if(S<=s&&e<=E)
        {
            uf.uni(mx[n],p);
            mg[n]=1;
            return;
        }
        int m=(s+e)/2;
        mrg(n*2,s,m,S,E,p);
        mrg(n*2+1,m+1,e,S,E,p);
        return;
    }
}st;
struct fen
{
    int t[200020];
    fen(){}
    inline void init()
    {
        fill(t,t+200020,0);
        return;
    }
    inline void fi(int x,int p)
    {
        for(x++;x<200020;x+=x&-x)
            t[x]+=p;
        return;
    }
    inline int fs(int x)
    {
        int s=0;
        for(x++;x>0;x=x&(x-1))
            s+=t[x];
        return s;
    }
}ft;
vector<int>vx,vy;
inline ll cpm(const vector<pair<pi,pi> >&v)
{
    int vxs=(int)vx.size();
    vector<vector<pi> >in(vxs),out(vxs);
    vector<vector<pair<pi,int> > >mrg(vxs);
    ll s=0;
    for(int i=0;i<(int)v.size();i++)
    {
        auto&t=v[i];
        if(t.fi.fi==t.se.fi)
            mrg[t.fi.fi].eb(pi(t.fi.se,t.se.se),i);
        else
        {
            in[t.fi.fi].eb(t.fi.se,i);
            out[t.se.fi].eb(t.fi.se,i);
        }
    }
    int m=(int)vy.size();
    uf.init();
    st.init();
    ft.init();
    for(int i=0;i<(int)vx.size();i++)
    {
        for(auto&t:in[i])
            st.set(1,0,m-1,t.fi,t.se),ft.fi(t.fi,1);
        for(auto&t:mrg[i])
            st.mrg(1,0,m-1,t.fi.fi,t.fi.se,t.se),s+=ft.fs(t.fi.se)-ft.fs(t.fi.fi-1);
        for(auto&t:out[i])
            st.set(1,0,m-1,t.fi,-1),ft.fi(t.fi,-1);
    }
    int cc=0;
    for(int i=0;i<(int)v.size();i++)
        if(uf.pa[i]==-1)
            cc++;
    return s+cc;
}
inline int sz(const vector<pair<pi,pi> >&v){return(int)v.size();}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int h,w,n;
    cin>>w>>h>>n;
    vx.eb(0),vx.eb(w);
    vy.eb(0),vy.eb(h);
    vector<pair<pi,pi> >edge;
    edge.eb(pi(0,0),pi(w,0));
    edge.eb(pi(0,0),pi(0,h));
    edge.eb(pi(w,0),pi(w,h));
    edge.eb(pi(0,h),pi(w,h));
    for(int i=0;i<n;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        edge.eb(pi(x1,y1),pi(x2,y2));
        vx.eb(x1),vx.eb(x2);
        vy.eb(y1),vy.eb(y2);
    }
    sort(all(vx)),vx.erase(unique(all(vx)),vx.end());
    sort(all(vy)),vy.erase(unique(all(vy)),vy.end());
    for(auto&t:edge)
    {
        t.fi.fi=lower_bound(all(vx),t.fi.fi)-vx.begin();
        t.fi.se=lower_bound(all(vy),t.fi.se)-vy.begin();
        t.se.fi=lower_bound(all(vx),t.se.fi)-vx.begin();
        t.se.se=lower_bound(all(vy),t.se.se)-vy.begin();
    }
    cout<<cpm(edge)-sz(edge)<<endl;
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50