oj.uz

Submission #12898

# Submission time Handle Problem Language Result Execution time Memory
12898 2015-01-19T06:15:30 Z baneling100 수족관 1 (KOI13_aqua1) C++
100 / 100
 4 ms 1192 KB 
#include <stdio.h>
#define INF 0x7fffffff

struct line {
    int X1;
    int X2;
    int Y;
    int Hole;
} Line[5000];
int N, K, Ans;

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

    int i, Min=INF, Mid, res1=0, res2=0;

    if(Left==Right) {
        if(Line[Left].Hole)
            return 1;
        Ans+=(Line[Left].Y-H)*(Line[Left].X2-Line[Left].X1);
        return 0;
    }
    else {
        for(i=Left ; i<=Right ; i++)
            if(Min>Line[i].Y) {
                Min=Line[i].Y;
                Mid=i;
            }
        if(Left<=Mid-1)
            res1=divideConquer(Left ,Mid-1,Min);
        if(Mid+1<=Right)
            res2=divideConquer(Mid+1,Right,Min);
        if(res1 || res2 || Line[Mid].Hole)
            return 1;
        Ans+=(Min-H)*(Line[Right].X2-Line[Left].X1);
        return 0;
    }
}

int main(void) {

    int i, j, in1, in2, in3, in4, temp;

    scanf("%d",&N);
    scanf("%d %d",&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};
    }
    scanf("%d %d %d",&in1,&in2,&K);
    for(i=1 ; i<=K ; i++) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        for(j=1 ; j<(N>>1) ; j++)
            if(Line[j].X1==in1 && Line[j].X2==in3 && Line[j].Y==in2) {
                Line[j].Hole=1;
                break;
            }
    }
    temp=divideConquer(1,(N>>1)-1,0);
    printf("%d",Ans);
    return 0;
}

Subtask #1
23.0 / 23.0

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

Subtask #2
19.0 / 19.0

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

Subtask #3
22.0 / 22.0

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

Subtask #4
36.0 / 36.0

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