Submission #12899

#	Time	Username	Problem	Language	Result	Execution time	Memory
12899		baneling100	수족관 2 (KOI13_aqua2)	C++98	13 / 100	144 ms	9480 KiB

aqua2

#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 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 35
• Subtask 4: 0 / 31