oj.uz

답안 #12899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
12899 2015-01-19T06:59:45 Z baneling100 수족관 2 (KOI13_aqua2) C++
13 / 100
 144 ms 9480 KB 
#include <stdio.h>
#define INF 0x7fffffff

struct line {
    int X1;
    int X2;
    int Y;
    int Hole;
} Line[150000];
struct idx {
    int Min;
    int Loc;
} Idx[524288];
int N, K, M, Check[500001];
int P, Q, U, V;
long long Rest;
double Time;

void idxTree(int L, int R, int Loc) {

    int M=(L+R)/2;

    if(U<=L && R<=V) {
        if(Q>Idx[Loc].Min) {
            Q=Idx[Loc].Min;
            P=Idx[Loc].Loc;
        }
    }
    else {
        if(U  <=M)
            idxTree(L  ,M,Loc<<1);
        if(M+1<=V)
            idxTree(M+1,R,(Loc<<1)+1);
    }
}

int divideConquer(int Left, int Right, int H) {

    int Mid, Min, num=0;

    if(Left==Right) {
        if(Line[Left].Hole) {
            Time+=((double)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H);
            return 1;
        }
        else {
            Rest+=((long long)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H);
            return 0;
        }
    }
    else {
        Q=INF;
        U=Left;
        V=Right;
        idxTree(1,M,1);
        Mid=P;
        Min=Q;
        if(Left<=Mid-1)
            num+=divideConquer(Left ,Mid-1,Min);
        if(Mid+1<=Right)
            num+=divideConquer(Mid+1,Right,Min);
        num+=Line[Mid].Hole;
        if(num)
            Time+=((double)Line[Right].X2-Line[Left].X1)*(Min-H)/num;
        else
            Rest+=((long long)Line[Right].X2-Line[Left].X1)*(Min-H);
        return num;
    }
}

int main(void) {

    int i, in1, in2, in3, in4, temp;

    scanf("%d %d %d",&N,&in1,&in2);
    for(i=2 ; i<N ; i+=2) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        Line[i>>1]={in1,in3,in2,0};
        Check[in1]=i>>1;
    }
    scanf("%d %d %d",&in1,&in2,&K);
    for(i=1 ; i<=K ; i++) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        Line[Check[in1]].Hole=1;
    }
    N=(N>>1)-1;
    for(M=1 ; M<N ; M<<=1);
    for(i=1 ; i<=N ; i++)
        Idx[M+i-1]={Line[i].Y,i};
    for(i=M+N ; i<2*M ; i++)
        Idx[i]={INF,0};
    for(i=M-1 ; i>=1 ; i--) {
        if(Idx[i<<1].Min<=Idx[(i<<1)+1].Min)
            Idx[i]={Idx[i<<1    ].Min,Idx[i<<1    ].Loc};
        else
            Idx[i]={Idx[(i<<1)+1].Min,Idx[(i<<1)+1].Loc};
    }
    temp=divideConquer(1,N,0);
    printf("%.2lf\n%lld",Time,Rest);

    return 0;
}

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 9480 KB Output is correct
2 Correct 0 ms 9480 KB Output is correct
3 Correct 0 ms 9480 KB Output is correct
4 Correct 0 ms 9480 KB Output is correct
5 Correct 0 ms 9480 KB Output is correct
6 Correct 0 ms 9480 KB Output is correct
7 Correct 0 ms 9480 KB Output is correct
8 Correct 0 ms 9480 KB Output is correct
9 Correct 0 ms 9480 KB Output is correct
10 Correct 0 ms 9480 KB Output is correct

Subtask #2
0.0 / 21.0

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

Subtask #3
0.0 / 35.0

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

Subtask #4
0.0 / 31.0

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