Submission #16849

#	Time	Username	Problem	Language	Result	Execution time	Memory
16849		hjk0553	수족관 1 (KOI13_aqua1)	C11	100 / 100	12 ms	1120 KiB

aqua1

#include<stdio.h>
#define Mn 5000
#define INF 40000
struct aqua
{
    int height;
    int count;
    int x;
    int y;
} data[Mn/2+1];
void process()
{
    int i;
    int j;
    int edgecount;
    int holeindex;
    int xedge1,yedge1,xedge2,yedge2;
    int holecount;
    int xhole,yhole;
    int minheight;
    int ans=0;
    scanf("%d",&edgecount);
    scanf("%d %d",&xedge1,&yedge1);
    for(i=1;i<edgecount/2;i++)
    {
        scanf("%d %d %d %d",&xedge1,&yedge1,&xedge2,&yedge2);
        data[i].count=xedge2-xedge1;
        data[i].x=xedge1;
        data[i].y=yedge1;
    }
    scanf("%d %d",&xedge1,&yedge1);
    scanf("%d",&holecount);
    for(i=1;i<=holecount;i++)
    {
        scanf("%d %d %d %d",&xhole,&yhole,&xedge1,&yedge1);
        int l=1,r=edgecount/2-1,m;
        while(l<=r)
        {
            m=(l+r)/2;
            if(data[m].x==xhole && data[m].y==yhole) break;
            if(xhole!=data[m].x)
            {
                if(xhole<data[m].x) r=m-1;
                    else l=m+1;
            }
            else if(yhole!=data[m].y)
            {
                if(yhole<data[m].y) r=m-1;
                    else l=m+1;
            }
        }
        holeindex=m;
        minheight=INF;
        for(j=holeindex;j>=1;j--)
        {
            if(minheight>data[j].y) minheight=data[j].y;
            if(data[j].height<minheight) data[j].height = minheight;
        }
        minheight=INF;
        for(j=holeindex;j<edgecount/2;j++)
        {
            if(minheight>data[j].y) minheight=data[j].y;
            if(data[j].height<minheight) data[j].height = minheight;
        }
    }
    for(i=1;i<edgecount/2;i++)
    {
        ans+=(data[i].y-data[i].height)*data[i].count;
    }
    printf("%d",ans);
}
int main()
{
    process();
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 22 / 22
• Subtask 4: 36 / 36