Submission #12907

#	Time	Username	Problem	Language	Result	Execution time	Memory
12907		baneling100	수족관 3 (KOI13_aqua3)	C++98	100 / 100	132 ms	19688 KiB

aqua3

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

using namespace std;

struct line {
    int X1;
    int X2;
    int Y;
} Line[150000];
priority_queue <long long> PQ;
int N, K, M, P, Q, R, Idx[524288];
long long Ans;

void getIdx(int Left, int Right, int Loc) {

    int Mid=(Left+Right)>>1;

    if(P<=Left && Right<=Q) {
        if(Line[R].Y>Line[Idx[Loc]].Y)
            R=Idx[Loc];
    }
    else {
        if(P<=Mid)
            getIdx(Left ,Mid  ,Loc<<1    );
        if(Mid+1<=Q)
            getIdx(Mid+1,Right,(Loc<<1)+1);
    }
}

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

    int Mid;
    long long Lcost=0, Rcost=0;

    if(Left==Right)
        return ((long long)Line[Left].X2-Line[Left].X1)*(Line[Left].Y-H);
    else {
        P=Left;
        Q=Right;
        R=0;
        getIdx(1,M,1);
        Mid=R;
        if(Left<=Mid-1)
            Lcost=divideConquer(Left ,Mid-1,Line[Mid].Y);
        if(Mid+1<=Right)
            Rcost=divideConquer(Mid+1,Right,Line[Mid].Y);
        PQ.push(min(Lcost,Rcost));
        return max(Lcost,Rcost)+((long long)Line[Right].X2-Line[Left].X1)*(Line[Mid].Y-H);
    }
}

int main(void) {

    int i, in1, in2, in3, in4;

    scanf("%d %d %d",&N,&in1,&in2);
    N=(N>>1)-1;
    for(i=1 ; i<=N ; i++) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        Line[i]={in1,in3,in2};
    }
    scanf("%d %d %d",&in1,&in2,&K);
    for(M=1 ; M<N ; M<<=1);
    Line[0].Y=INF;
    for(i=M ; i<M+N ; i++)
        Idx[i]=i-M+1;
    for(i=M-1 ; i>=1 ; i--) {
        if(Line[Idx[i<<1]].Y<=Line[Idx[(i<<1)+1]].Y)
            Idx[i]=Idx[i<<1];
        else
            Idx[i]=Idx[(i<<1)+1];
    }
    PQ.push(divideConquer(1,N,0));
    for(i=1 ; i<=K && !PQ.empty() ; i++) {
        Ans+=PQ.top();
        PQ.pop();
    }
    printf("%lld",Ans);
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16