Submission #96425

#	Time	Username	Problem	Language	Result	Execution time	Memory
96425		easrui	절취선 (JOI14_ho_t5)	C++14	100 / 100	302 ms	14432 KiB

2014_ho_t5

#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;
long long inter;
bool ch[MN];
pii T[8*MN];
vector<int> X,Y;

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(s!=e){
            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){
      	if(v==-1 && !c) comp++;
        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 act(int l, int r, int s, int e, int pos)
{
    if(r<s || l>e) return 0;
    int c = T[pos].col;
    if(c){
        if(s!=e){
            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 T[pos].sz;
    }
    int m = (s+e)/2;
    return act(l,r,s,m,2*pos)+act(l,r,m+1,e,2*pos+1);
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    //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;
            inter += act(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 << inter+comp-N-4;
}

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