oj.uz

Submission #55210

# Submission time Handle Problem Language Result Execution time Memory
55210 2018-07-06T10:34:52 Z 노영훈(#1526) None (JOI14_ho_t5) C++11
30 / 100
 3000 ms 111832 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];

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> H0[XMX];
vector<int> V0;
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){
            V0.push_back(i);
            continue;
        }
        H0[l.x1].push_back(i+1);
        H0[l.x2+1].push_back(-i-1);
    }
    sort(V0.begin(), V0.end(), [](int a, int b){
        return L[a].x1<L[b].x1;
    });
    int x=0;
    for(int i:V0){
        line &l=L[i];
        while(x<l.x1){
            x++;
            for(int idx:H0[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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 56696 KB Output is correct
2 Correct 46 ms 56804 KB Output is correct
3 Correct 45 ms 56880 KB Output is correct
4 Correct 48 ms 56960 KB Output is correct
5 Correct 47 ms 57032 KB Output is correct
6 Correct 46 ms 57032 KB Output is correct
7 Correct 48 ms 57160 KB Output is correct
8 Correct 59 ms 57416 KB Output is correct
9 Correct 51 ms 57416 KB Output is correct
10 Correct 59 ms 57416 KB Output is correct
11 Correct 85 ms 57672 KB Output is correct
12 Correct 60 ms 57672 KB Output is correct
13 Correct 70 ms 57672 KB Output is correct
14 Correct 55 ms 57672 KB Output is correct
15 Correct 66 ms 57712 KB Output is correct
16 Correct 52 ms 57712 KB Output is correct
17 Correct 54 ms 57712 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 56696 KB Output is correct
2 Correct 46 ms 56804 KB Output is correct
3 Correct 45 ms 56880 KB Output is correct
4 Correct 48 ms 56960 KB Output is correct
5 Correct 47 ms 57032 KB Output is correct
6 Correct 46 ms 57032 KB Output is correct
7 Correct 48 ms 57160 KB Output is correct
8 Correct 59 ms 57416 KB Output is correct
9 Correct 51 ms 57416 KB Output is correct
10 Correct 59 ms 57416 KB Output is correct
11 Correct 85 ms 57672 KB Output is correct
12 Correct 60 ms 57672 KB Output is correct
13 Correct 70 ms 57672 KB Output is correct
14 Correct 55 ms 57672 KB Output is correct
15 Correct 66 ms 57712 KB Output is correct
16 Correct 52 ms 57712 KB Output is correct
17 Correct 54 ms 57712 KB Output is correct
18 Correct 53 ms 57712 KB Output is correct
19 Correct 60 ms 57712 KB Output is correct
20 Correct 51 ms 57712 KB Output is correct
21 Correct 65 ms 57712 KB Output is correct
22 Correct 54 ms 57712 KB Output is correct
23 Correct 63 ms 57712 KB Output is correct
24 Correct 79 ms 57788 KB Output is correct
25 Correct 56 ms 57788 KB Output is correct
26 Correct 60 ms 57788 KB Output is correct
27 Correct 84 ms 57788 KB Output is correct
28 Correct 73 ms 57788 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 57788 KB Output is correct
2 Correct 68 ms 57788 KB Output is correct
3 Correct 60 ms 57788 KB Output is correct
4 Correct 51 ms 57788 KB Output is correct
5 Correct 109 ms 61036 KB Output is correct
6 Correct 487 ms 78376 KB Output is correct
7 Correct 1128 ms 102276 KB Output is correct
8 Correct 1060 ms 102276 KB Output is correct
9 Correct 838 ms 104548 KB Output is correct
10 Correct 746 ms 104548 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 104548 KB Output is correct
2 Correct 80 ms 104548 KB Output is correct
3 Correct 2704 ms 104548 KB Output is correct
4 Correct 53 ms 104548 KB Output is correct
5 Correct 75 ms 104548 KB Output is correct
6 Execution timed out 3057 ms 111832 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 56696 KB Output is correct
2 Correct 46 ms 56804 KB Output is correct
3 Correct 45 ms 56880 KB Output is correct
4 Correct 48 ms 56960 KB Output is correct
5 Correct 47 ms 57032 KB Output is correct
6 Correct 46 ms 57032 KB Output is correct
7 Correct 48 ms 57160 KB Output is correct
8 Correct 59 ms 57416 KB Output is correct
9 Correct 51 ms 57416 KB Output is correct
10 Correct 59 ms 57416 KB Output is correct
11 Correct 85 ms 57672 KB Output is correct
12 Correct 60 ms 57672 KB Output is correct
13 Correct 70 ms 57672 KB Output is correct
14 Correct 55 ms 57672 KB Output is correct
15 Correct 66 ms 57712 KB Output is correct
16 Correct 52 ms 57712 KB Output is correct
17 Correct 54 ms 57712 KB Output is correct
18 Correct 53 ms 57712 KB Output is correct
19 Correct 60 ms 57712 KB Output is correct
20 Correct 51 ms 57712 KB Output is correct
21 Correct 65 ms 57712 KB Output is correct
22 Correct 54 ms 57712 KB Output is correct
23 Correct 63 ms 57712 KB Output is correct
24 Correct 79 ms 57788 KB Output is correct
25 Correct 56 ms 57788 KB Output is correct
26 Correct 60 ms 57788 KB Output is correct
27 Correct 84 ms 57788 KB Output is correct
28 Correct 73 ms 57788 KB Output is correct
29 Correct 49 ms 57788 KB Output is correct
30 Correct 68 ms 57788 KB Output is correct
31 Correct 60 ms 57788 KB Output is correct
32 Correct 51 ms 57788 KB Output is correct
33 Correct 109 ms 61036 KB Output is correct
34 Correct 487 ms 78376 KB Output is correct
35 Correct 1128 ms 102276 KB Output is correct
36 Correct 1060 ms 102276 KB Output is correct
37 Correct 838 ms 104548 KB Output is correct
38 Correct 746 ms 104548 KB Output is correct
39 Correct 47 ms 104548 KB Output is correct
40 Correct 80 ms 104548 KB Output is correct
41 Correct 2704 ms 104548 KB Output is correct
42 Correct 53 ms 104548 KB Output is correct
43 Correct 75 ms 104548 KB Output is correct
44 Execution timed out 3057 ms 111832 KB Time limit exceeded
45 Halted 0 ms 0 KB -