oj.uz

Submission #12900

# Submission time Handle Problem Language Result Execution time Memory
12900 2015-01-19T07:39:32 Z baneling100 수족관 2 (KOI13_aqua2) C++
100 / 100
 168 ms 28108 KB 
#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.0 / 13.0

# Verdict Execution time Memory 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
21.0 / 21.0

# Verdict Execution time Memory 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 #3
35.0 / 35.0

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

Subtask #4
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 9480 KB Output is correct
2 Correct 116 ms 9480 KB Output is correct
3 Correct 168 ms 13100 KB Output is correct
4 Correct 148 ms 13096 KB Output is correct
5 Correct 160 ms 13108 KB Output is correct
6 Correct 136 ms 28108 KB Output is correct
7 Correct 160 ms 18728 KB Output is correct
8 Correct 120 ms 18732 KB Output is correct
9 Correct 124 ms 9480 KB Output is correct
10 Correct 148 ms 9480 KB Output is correct