Submission #874006

#	Time	Username	Problem	Language	Result	Execution time	Memory
874006		azberjibiou	절취선 (JOI14_ho_t5)	C++17	100 / 100	194 ms	42524 KiB

2014_ho_t5

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define piii pair<pair<int, int>, pair<int, int>>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=210005;
const int mxM=500004;
const int mxK=30;
const int MOD=1'000'000'007;
const ll INF=8e18;
const pii tsh=pii(MOD, 0);
typedef struct minmax_seg{
    pii seg[4*mxN];
    int n;
    void set_n(int m){n=m;}
    void init(){for(int i=0;i<4*mxN;i++) seg[i]=tsh;}
    pii f(pii a, pii b){return pii(min(a.fi, b.fi), max(a.se, b.se));}
    void upd(int idx, int s, int e, int pos, pii val){
        if(s==e){
            seg[idx]=val;
            return;
        }
        int mid=(s+e)/2;
        if(pos<=mid) upd(2*idx, s, mid, pos, val);
        else upd(2*idx+1, mid+1, e, pos, val);
        seg[idx]=f(seg[2*idx], seg[2*idx+1]);
    }
    pii solv(int idx, int s1, int e1, int s2, int e2){
        if(s2>e1 || s1>e2)  return tsh;
        if(s2<=s1 && e1<=e2)    return seg[idx];
        int mid=(s1+e1)/2;
        return f(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
    }
    void upd(int pos, pii val){return upd(1, 1, n, pos, val);}
    pii solv(int s, int e){return solv(1, 1, n, s, e);}
}minmax_seg;
typedef struct BIT{
    int fen[mxN], n;
    void set_n(int m){n=m;}
    void upd(int idx, int val){for(;idx<=n;idx+=(idx&(-idx))) fen[idx]+=val;}
    int sum(int idx){int res=0; for(;idx>0;idx-=(idx&(-idx))) res+=fen[idx]; return res;}
    int solv(int s, int e){return sum(e)-sum(s-1);}
}BIT;
typedef struct line{
    ll x1, x2, y, xy;   ///xy=1: x축과 평행 2: y축과 평행
    line() : x1(), x2(), y(), xy() {}
    line(ll x1, ll x2, ll y, ll xy) : x1(x1), x2(x2), y(y), xy(xy) {}
}line;
int N;
ll H, W;
vector <line> v;
vector <line> ev;
BIT T1;
minmax_seg T2;
ll cntV, cntE, cntC;
void input(){
    cin >> W >> H >> N;
    v.emplace_back(0, W, 0, 1);
    v.emplace_back(0, W, H, 1);
    v.emplace_back(0, H, 0, 2);
    v.emplace_back(0, H, W, 2);
    for(int i=1;i<=N;i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a==c)    v.emplace_back(b, d, c, 2);
        else    v.emplace_back(a, c, b, 1);
    }
}
void coor_comp(){
    vector <ll> crx, cry;
    for(auto &[x1, x2, y, xy] : v){
        x1=3*x1-1, x2=3*x2+1, y=3*y;
        if(xy==1)   crx.push_back(x1), crx.push_back(x2), cry.push_back(y);
        else    cry.push_back(x1), cry.push_back(x2), crx.push_back(y);
    }
    sort(all(crx));
    crx.erase(unique(all(crx)), crx.end());
    sort(all(cry));
    cry.erase(unique(all(cry)), cry.end());
    for(auto &[x1, x2, y, xy] : v){
        if(xy==1){
            x1=lower_bound(all(crx), x1)-crx.begin()+1;
            x2=lower_bound(all(crx), x2)-crx.begin()+1;
            y=lower_bound(all(cry), y)-cry.begin()+1;
        }
        else{
            x1=lower_bound(all(cry), x1)-cry.begin()+1;
            x2=lower_bound(all(cry), x2)-cry.begin()+1;
            y=lower_bound(all(crx), y)-crx.begin()+1;
        }
        if(xy==1) ev.emplace_back(x1, x2, y, xy);
        else ev.emplace_back(y, 1, x1, xy), ev.emplace_back(y, -1, x2, xy);
    }
    W=crx.size(), H=cry.size();
    sort(all(ev), [](line a, line b){return a.y<b.y;});
}
void count_VE(){
    T1.set_n(W);
    cntV=2*(N+4);
    for(auto [x1, x2, y, xy] : ev){
        if(xy==1) cntV+=T1.solv(x1, x2);
        else T1.upd(x1, x2);
        //printf("x1=%d, x2=%d, y=%d, xy=%d\n", x1, x2, y, xy);
    }
    //2*(N+4)+4*(cntV-2*(N+4))=2*cntE
    cntE=2*cntV-3*(N+4);
}
int ci=1; //component index
set <int> s[mxN];   //x coordinate
void count_comp(){
    T2.set_n(W);
    T2.init();
    for(auto [x1, x2, y, xy] : ev){
        //printf("x1=%d, x2=%d, y=%d, xy=%d\n", x1, x2, y, xy);
        if(xy==1){
            pii res=T2.solv(x1, x2);
            if(res==tsh){
                cntC++;
                continue;
            }
            for(;res.fi!=res.se;res=T2.solv(x1, x2)){
                int i1=res.fi, i2=res.se;
                if(s[i1].size()>s[i2].size())   swap(i1, i2);
                for(int ele : s[i1]){
                    T2.upd(ele, pii(i2, i2));
                    s[i2].insert(ele);
                }
                s[i1].clear();
                cntC--;
            }
        }
        else{
            if(x2==1){
                cntC++;
                T2.upd(x1, pii(ci, ci));
                s[ci].insert(x1);
                ci++;
            }
            else{
                int col=T2.solv(x1, x1).fi;
                T2.upd(x1, tsh);
                s[col].erase(x1);
            }
        }
    }
}
int main()
{
    gibon
    input();
    coor_comp();
    count_VE();
    //V-E+F=2
    //printf("cntE=%lld, cntV=%lld\n", cntE, cntV);
    count_comp();
    cout << cntE-cntV+cntC;
}

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