oj.uz

답안 #55189

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
55189 2018-07-06T09:16:23 Z 노영훈(#1526) 절취선 (JOI14_ho_t5) C++11
20 / 100
 498 ms 54560 KB 
#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];


// somehow update pst

// somehow query on pst. constant x, y1~y2 (vert)

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;


int U[MX];
int components(){
    return 1;
}



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;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 14824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 14824 KB Output is correct
2 Correct 17 ms 14824 KB Output is correct
3 Correct 52 ms 18152 KB Output is correct
4 Correct 15 ms 18152 KB Output is correct
5 Correct 17 ms 18152 KB Output is correct
6 Correct 498 ms 54560 KB Output is correct
7 Correct 34 ms 54560 KB Output is correct
8 Correct 264 ms 54560 KB Output is correct
9 Correct 263 ms 54560 KB Output is correct
10 Correct 327 ms 54560 KB Output is correct

Subtask #5
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 14456 KB Output isn't correct
2 Halted 0 ms 0 KB -