oj.uz

Submission #95873

# Submission time Handle Problem Language Result Execution time Memory
95873 2019-02-03T09:49:27 Z easrui None (JOI14_ho_t5) C++14
10 / 100
 484 ms 263168 KB 
#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[4*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(T[2*pos].sz) join(T[2*pos].col,c);
        if(T[2*pos+1].sz) join(T[2*pos+1].col,c);
        if(s!=e){
     		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 sum(int l, int r, int s, int e, int pos)
{
    if(l>r) return 0;
    if(r<s || e<l) return 0;
    if(l<=s && e<=r) return T[pos].sz;
    int m = (s+e)/2;
    return sum(l,r,s,m,2*pos)+sum(l,r,m+1,e,2*pos+1);
}

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

int main()
{
    //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;
            act(E[i].s,E[i].e,0,Y.size()-1,1);
            inter += sum(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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 4 ms 380 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 4 ms 380 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 504 KB Output is correct
22 Correct 4 ms 504 KB Output is correct
23 Correct 4 ms 376 KB Output is correct
24 Correct 4 ms 504 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 4 ms 376 KB Output is correct
27 Correct 5 ms 504 KB Output is correct
28 Correct 5 ms 504 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 504 KB Output is correct
5 Correct 31 ms 1272 KB Output is correct
6 Incorrect 183 ms 5612 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 32 ms 1368 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Runtime error 484 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 4 ms 376 KB Output is correct
12 Correct 3 ms 376 KB Output is correct
13 Correct 4 ms 376 KB Output is correct
14 Correct 4 ms 380 KB Output is correct
15 Correct 4 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct
21 Correct 4 ms 504 KB Output is correct
22 Correct 4 ms 504 KB Output is correct
23 Correct 4 ms 376 KB Output is correct
24 Correct 4 ms 504 KB Output is correct
25 Correct 5 ms 376 KB Output is correct
26 Correct 4 ms 376 KB Output is correct
27 Correct 5 ms 504 KB Output is correct
28 Correct 5 ms 504 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Correct 3 ms 376 KB Output is correct
31 Correct 3 ms 376 KB Output is correct
32 Correct 4 ms 504 KB Output is correct
33 Correct 31 ms 1272 KB Output is correct
34 Incorrect 183 ms 5612 KB Output isn't correct
35 Halted 0 ms 0 KB -