oj.uz

Submission #12907

# Submission time Handle Problem Language Result Execution time Memory
12907 2015-01-19T14:44:19 Z baneling100 수족관 3 (KOI13_aqua3) C++
100 / 100
 132 ms 19688 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5016 KB Output is correct
2 Correct 0 ms 5016 KB Output is correct
3 Correct 0 ms 5016 KB Output is correct
4 Correct 0 ms 5016 KB Output is correct
5 Correct 0 ms 5016 KB Output is correct
6 Correct 0 ms 5016 KB Output is correct
7 Correct 0 ms 5016 KB Output is correct
8 Correct 0 ms 5016 KB Output is correct
9 Correct 0 ms 5016 KB Output is correct
10 Correct 0 ms 5016 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5016 KB Output is correct
2 Correct 0 ms 5016 KB Output is correct
3 Correct 0 ms 5016 KB Output is correct
4 Correct 0 ms 5016 KB Output is correct
5 Correct 0 ms 5016 KB Output is correct
6 Correct 0 ms 5088 KB Output is correct
7 Correct 0 ms 5016 KB Output is correct
8 Correct 0 ms 5016 KB Output is correct
9 Correct 0 ms 5016 KB Output is correct
10 Correct 0 ms 5016 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5788 KB Output is correct
2 Correct 84 ms 5788 KB Output is correct
3 Correct 120 ms 8776 KB Output is correct
4 Correct 104 ms 8780 KB Output is correct
5 Correct 104 ms 8788 KB Output is correct
6 Correct 124 ms 19688 KB Output is correct
7 Correct 108 ms 12292 KB Output is correct
8 Correct 116 ms 12292 KB Output is correct
9 Correct 104 ms 6556 KB Output is correct
10 Correct 104 ms 6556 KB Output is correct
11 Correct 124 ms 19688 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 5788 KB Output is correct
2 Correct 88 ms 5788 KB Output is correct
3 Correct 100 ms 8772 KB Output is correct
4 Correct 112 ms 8764 KB Output is correct
5 Correct 108 ms 8772 KB Output is correct
6 Correct 132 ms 19688 KB Output is correct
7 Correct 108 ms 12292 KB Output is correct
8 Correct 104 ms 12288 KB Output is correct
9 Correct 112 ms 6556 KB Output is correct
10 Correct 96 ms 6556 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 5788 KB Output is correct
2 Correct 88 ms 5788 KB Output is correct
3 Correct 128 ms 8772 KB Output is correct
4 Correct 108 ms 8780 KB Output is correct
5 Correct 104 ms 8768 KB Output is correct
6 Correct 112 ms 12288 KB Output is correct
7 Correct 124 ms 12292 KB Output is correct
8 Correct 104 ms 6556 KB Output is correct
9 Correct 100 ms 6556 KB Output is correct