Submission #12900

#	Time	Username	Problem	Language	Result	Execution time	Memory
12900		baneling100	수족관 2 (KOI13_aqua2)	C++98	100 / 100	168 ms	28108 KiB

aqua2

#include <stdio.h>
#include <algorithm>
#define INF 0x7fffffff

using namespace std;

typedef pair <int,double> ppair;
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;

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

    int M=(L+R)/2;

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

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

    int Mid, Min, Num=0;
    double Time=0;
    ppair temp;

    if(Left==Right) {
        if(Line[Left].Hole) {
            ((double)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H);
            return make_pair(1,((double)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H));
        }
        else {
            Rest+=((long long)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H);
            return make_pair(0,0);
        }
    }
    else {
        Q=INF;
        U=Left;
        V=Right;
        idxTree(1,M,1);
        Mid=P;
        Min=Q;
        if(Left<=Mid-1) {
            temp=divideConquer(Left ,Mid-1,Min);
            Num+=temp.first;
            Time=max(Time,temp.second);
        }
        if(Mid+1<=Right) {
            temp=divideConquer(Mid+1,Right,Min);
            Num+=temp.first;
            Time=max(Time,temp.second);
        }
        Num+=Line[Mid].Hole;
        if(Num)
            return make_pair(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 make_pair(0,0);
        }
    }
}

int main(void) {

    int i, in1, in2, in3, in4;
    ppair 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",temp.second,Rest);

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31