oj.uz

답안 #123039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
123039 2019-06-30T05:42:33 Z ansol4328 수족관 2 (KOI13_aqua2) C++11
100 / 100
 721 ms 51300 KB 
#include<stdio.h>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

const int INF=1e9;

struct SegTree
{
    vector<int> hole, lwall, rwall, wheight, wlazy;
    vector<double> time, lazy;
    int base;
    SegTree(int a)
    {
        base=1;
        while(base<a) base<<=1;
        hole.resize(base*2+2);
        lwall.resize(base*2+2); //maximize
        rwall.resize(base*2+2,INF); //minimize
        time.resize(base*2+2);
        lazy.resize(base*2+2);
        wheight.resize(base*2+2);
        wlazy.resize(base*2+2);
        base--;
    }
    void update_hole(int idx, int val)
    {
        idx+=base;
        hole[idx]+=val;
        idx>>=1;
        while(idx!=0)
        {
            hole[idx]=hole[idx*2]+hole[idx*2+1];
            idx>>=1;
        }
    }
    int hole_num(int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        if(nf<st || fn<ns) return 0;
        if(st<=ns && nf<=fn) return hole[num];
        int mid=(ns+nf)>>1;
        return hole_num(st,fn,ns,mid,num*2)+hole_num(st,fn,mid+1,nf,num*2+1);
    }
    int get_lwall(int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        if(nf<st || fn<ns) return 0;
        if(st<=ns && nf<=fn) return lwall[num];
        int mid=(ns+nf)>>1;
        return max(get_lwall(st,fn,ns,mid,num*2),get_lwall(st,fn,mid+1,nf,num*2+1));
    }
    void update_wall(int idx)
    {
        int val=idx;
        idx+=base;
        lwall[idx]=val;
        rwall[idx]=val;
        idx>>=1;
        while(idx!=0)
        {
            lwall[idx]=max(lwall[idx*2],lwall[idx*2+1]);
            rwall[idx]=min(rwall[idx*2],rwall[idx*2+1]);
            idx>>=1;
        }
    }
    int get_rwall(int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        if(nf<st || fn<ns) return INF;
        if(st<=ns && nf<=fn) return rwall[num];
        int mid=(ns+nf)>>1;
        return min(get_rwall(st,fn,ns,mid,num*2),get_rwall(st,fn,mid+1,nf,num*2+1));
    }
    void propagate(int ns, int nf, int num)
    {
        if(lazy[num]!=0)
        {
            if(ns<nf)
            {
                lazy[num*2]+=lazy[num];
                lazy[num*2+1]+=lazy[num];
            }
            time[num]+=lazy[num];
            lazy[num]=0;
        }
    }
    void add_time(double val, int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        propagate(ns,nf,num);
        if(nf<st || fn<ns) return;
        if(st<=ns && nf<=fn)
        {
            lazy[num]=val;
            propagate(ns,nf,num);
            return;
        }
        int mid=(ns+nf)>>1;
        add_time(val,st,fn,ns,mid,num*2);
        add_time(val,st,fn,mid+1,nf,num*2+1);
        time[num]=time[num*2]+time[num*2+1];
    }
    void pro_height(int ns, int nf, int num)
    {
        if(wlazy[num]!=0)
        {
            if(ns<nf)
            {
                wlazy[num*2]=max(wlazy[num*2],wlazy[num]);
                wlazy[num*2+1]=max(wlazy[num*2+1],wlazy[num]);
            }
            wheight[num]=max(wheight[num],wlazy[num]);
            wlazy[num]=0;
        }
    }
    void change_height(int val, int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        pro_height(ns,nf,num);
        if(nf<st || fn<ns) return;
        if(st<=ns && nf<=fn)
        {
            wlazy[num]=max(wlazy[num],val);
            pro_height(ns,nf,num);
            return;
        }
        int mid=(ns+nf)>>1;
        change_height(val,st,fn,ns,mid,num*2);
        change_height(val,st,fn,mid+1,nf,num*2+1);
        wheight[num]=max(wheight[num*2],wheight[num*2+1]);
    }
    int get_height(int st, int fn, int ns=1, int nf=-1, int num=1)
    {
        if(nf==-1) nf=base+1;
        pro_height(ns,nf,num);
        if(nf<st || fn<ns) return 0;
        if(st<=ns && nf<=fn) return wheight[num];
        int mid=(ns+nf)>>1;
        return max(get_height(st,fn,ns,mid,num*2),get_height(st,fn,mid+1,nf,num*2+1));
    }
};

struct in
{
    int st, fn, height;
    in() {}
    in(int a, int b, int c) : st(a), fn(b), height(c) {}
};

bool cmp(const in &x, const in &y)
{
    return x.height<y.height || (x.height==y.height && x.st<y.st);
}

int n;
int m[300005][2], h, w;
in line[150005];
int hn, hcnt[500005];

int main()
{
    int c=0;
    ll tot=0;
    scanf("%d",&n);
    scanf("%d %d",&m[1][0],&m[1][1]);
    m[1][0]++;
    for(int i=2 ; i<n ; i+=2)
    {
        scanf("%d %d",&m[i][0],&m[i][1]);
        scanf("%d %d",&m[i+1][0],&m[i+1][1]);
        m[i][0]++, m[i+1][0]++;
        line[++c]=in(m[i][0],m[i+1][0],m[i][1]);
        tot+=(ll)(m[i+1][0]-m[i][0])*(ll)m[i][1];
    }
    scanf("%d %d",&m[n][0],&m[n][1]);
    m[n][0]++;
    w=m[n][0];
    scanf("%d",&hn);
    for(int i=1 ; i<=hn ; i++)
    {
        int x1, y1, x2 ,y2;
        scanf("%d %d",&x1,&y1);
        scanf("%d %d",&x2,&y2);
        x1++, x2++;
        hcnt[x1]++;
    }

    SegTree T(w);
    for(int i=1 ; i<=w ; i++)
    {
        if(hcnt[i]!=0) T.update_hole(i,hcnt[i]);
    }
    sort(line+1,line+1+c,cmp);
    T.update_wall(1);
    T.update_wall(w);
    int idx=1;
    while(idx<=c)
    {
        ll leak=0;
        ll cur_height=line[idx].height;
        queue<P> Q;
        int l=-1, r=-1;
        do
        {
            int st=line[idx].st, fn=line[idx].fn;
            int lw=T.get_lwall(1,st);
            int rw=T.get_rwall(fn,w);
            ll wh=T.get_height(lw,rw-1);
            Q.push(P(st,fn));
            if(l!=lw)
            {
                l=lw, r=rw;
                int hole_num=T.hole_num(l,r-1);
                if(hole_num>0)
                {
                    ll block=(ll)(r-l)*(cur_height-wh);
                    leak+=block;
                    double val=(double)block/hole_num;
                    T.add_time(val,l,r-1);
                    T.change_height((int)cur_height,l,r-1);
                }
            }
            idx++;
        }while(line[idx].height==line[idx-1].height);
        tot-=leak;
        while(!Q.empty())
        {
            P wval=Q.front();
            Q.pop();
            T.update_wall(wval.first);
            T.update_wall(wval.second);
        }
    }
    int base=T.base, num=0;
    for(int len=base+1 ; len>=1 ; len>>=1)
    {
        for(int st=1 ; st<=base-len+2 ; st+=len)
        {
            int fn=st+len-1;
            num++;
            T.propagate(st,fn,num);
        }
    }
    double rest=0;
    for(int i=1 ; i<=w ; i++) if(hcnt[i]!=0) rest=max(rest,T.time[i+base]);
    printf("%.2lf\n",rest);
    printf("%lld",tot);
    return 0;
}

Compilation message

aqua2.cpp: In function 'int main()':
aqua2.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua2.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m[1][0],&m[1][1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:175:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&m[i][0],&m[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:176:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&m[i+1][0],&m[i+1][1]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:181:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m[n][0],&m[n][1]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua2.cpp:184:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&hn);
     ~~~~~^~~~~~~~~~
aqua2.cpp:188:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x1,&y1);
         ~~~~~^~~~~~~~~~~~~~~~~
aqua2.cpp:189:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x2,&y2);
         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 380 KB Output is correct
10 Correct 2 ms 376 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 39288 KB Output is correct
2 Correct 48 ms 38652 KB Output is correct
3 Correct 48 ms 39416 KB Output is correct
4 Correct 45 ms 38392 KB Output is correct
5 Correct 48 ms 39160 KB Output is correct
6 Correct 52 ms 39416 KB Output is correct
7 Correct 47 ms 39416 KB Output is correct
8 Correct 46 ms 39416 KB Output is correct
9 Correct 49 ms 39032 KB Output is correct
10 Correct 46 ms 38008 KB Output is correct

Subtask #4
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 643 ms 43260 KB Output is correct
2 Correct 619 ms 48636 KB Output is correct
3 Correct 483 ms 50588 KB Output is correct
4 Correct 445 ms 49924 KB Output is correct
5 Correct 500 ms 50720 KB Output is correct
6 Correct 573 ms 47608 KB Output is correct
7 Correct 389 ms 51300 KB Output is correct
8 Correct 304 ms 48648 KB Output is correct
9 Correct 721 ms 49912 KB Output is correct
10 Correct 680 ms 49332 KB Output is correct