Submission #123045

# Submission time Handle Problem Language Result Execution time Memory
123045 2019-06-30T05:48:11 Z ansol4328 수족관 1 (KOI13_aqua1) C++11
100 / 100
12 ms 3324 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;
    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
        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 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;
                    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);
        }
    }
    printf("%lld",tot);
    return 0;
}

Compilation message

aqua1.cpp: In function 'int main()':
aqua1.cpp:138:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
aqua1.cpp:139: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]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:143: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]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:144: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]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:149: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]);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua1.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&hn);
     ~~~~~^~~~~~~~~~
aqua1.cpp:156:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x1,&y1);
         ~~~~~^~~~~~~~~~~~~~~~~
aqua1.cpp:157:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&x2,&y2);
         ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 256 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 376 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 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 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 380 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 9 ms 3324 KB Output is correct
2 Correct 10 ms 3192 KB Output is correct
3 Correct 10 ms 3192 KB Output is correct
4 Correct 10 ms 3320 KB Output is correct
5 Correct 10 ms 3192 KB Output is correct
6 Correct 12 ms 3268 KB Output is correct
7 Correct 9 ms 3292 KB Output is correct
8 Correct 8 ms 3192 KB Output is correct
9 Correct 10 ms 3192 KB Output is correct
10 Correct 10 ms 3192 KB Output is correct