Submission #18638

#	Time	Username	Problem	Language	Result	Execution time	Memory
18638		hjk0553	수족관 2 (KOI13_aqua2)	C++98	100 / 100	189 ms	27636 KiB

aqua2

#include<bits/stdc++.h>
#define N 333333
int n,k;
long long ans;
struct d{
    int idx;
    int height;
}
tree[N*3-1];
struct data{
    int x1;
    int y1;
    int x2;
    int y2;
    int hole;
}a[N];
int top;
int base;
struct d2{
    int gop;
    double second;
};
int fnd(int s,int e){
    int x,y;
    x=s+base-1;
    y=e+base-1;
    int rv,minhe=(int)2e9;
    while(x<y){
        if(x%2==1){
            if(minhe>tree[x].height){
                minhe=tree[x].height;
                rv=tree[x].idx;
            }
            x++;
        }
        if(y%2==0){
            if(minhe>tree[y].height){
                minhe=tree[y].height;
                rv=tree[y].idx;
            }
            y--;
        }
        x/=2;
        y/=2;
    }
    if(x==y){
        if(minhe>tree[x].height){
                minhe=tree[x].height;
                rv=tree[x].idx;
        }
    }
    return rv;
}
d2 f(int l,int r,int lastm){
    d2 rv;
    if(l==r){
        if(a[l].hole){
            double second=((double)a[r].x2-(double)a[l].x1)*((double)a[r].y2-(double)lastm);
            rv.gop=1;
            rv.second=second;
            return rv;
        }
        else{
            ans+=(a[r].x2-a[l].x1)*(a[r].y2-lastm);
            rv.gop=0;
            rv.second=(double)0;
            return rv;
        }
    }
    else{
        int i,m,idx;
        d2 a1={0,(double)0};
        d2 b1={0,(double)0};
        int flag=1,holechk=0;
        idx=fnd(l,r);
        m=a[idx].y1;
        if(a[idx].hole) holechk=1;
        if(idx+1<=r)
        a1=f(idx+1,r,m);
        if(idx-1>=l)
        b1=f(l,idx-1,m);
        if(a1.gop || b1.gop || holechk) flag=0;
        int gop=0;
        if(a1.gop>0) gop+=a1.gop;
        if(b1.gop>0) gop+=b1.gop;
        gop+=a[idx].hole;
        if(flag) ans+=(a[r].x2-a[l].x1)*(m-lastm);
        rv.gop=gop;
        rv.second=std::max(a1.second,b1.second);
        if(gop>0) rv.second+=((double)a[r].x2-(double)a[l].x1)*((double)m-(double)lastm)/(double)gop;
        return rv;
    }
}
int main(){
    int i,y1,x1,y2,x2;
    scanf("%d",&n);
    for(base=1;base<n/2-1;base*=2);
    scanf("%d %d",&x1,&y1);
    for(i=1;i<n/2;i++){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        top++;
        a[top]={x1,y1,x2,y2};
        tree[i+base-1].height=y1;
        tree[i+base-1].idx=i;
    }
    for(i=base-1;i>=1;i--){
        if(tree[i*2].height<tree[i*2+1].height){
            tree[i].height=tree[i*2].height;
            tree[i].idx=tree[i*2].idx;
        }
        else{
            tree[i].height=tree[i*2+1].height;
            tree[i].idx=tree[i*2+1].idx;
        }
    }
    scanf("%d %d",&x1,&y1);
    scanf("%d",&k);
    for(i=1;i<=k;i++){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        int l=1,r=n/2-1,m;
        while(l<=r){
            m=(l+r)/2;
            if(a[m].x2==x2) break;
            a[m].x2>x2?r=m-1:l=m+1;
        }
        a[m].hole=1;
    }
    d2 time=f(1,n/2-1,0);
    printf("%3.2f\n%lld",time.second,ans);
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31