oj.uz

Submission #321305

# Submission time Handle Problem Language Result Execution time Memory
321305 2020-11-12T02:56:05 Z ansol4328 수족관 3 (KOI13_aqua3) C++14
100 / 100
 445 ms 78768 KB 
#include<bits/stdc++.h>

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

struct A{
    ll sx, fx, h;
    A(){}
    A(ll a, ll b, ll c) : sx(a), fx(b), h(c) {}
};

struct uf{
    vector<int> par;
    vector<ll> h, sx, fx;
    uf(int a, A arr[]){
        par.resize(a+5,-1);
        h.resize(a+5);
        sx.resize(a+5);
        fx.resize(a+5);
        for(int i=1 ; i<=a ; i++) h[i]=arr[i].h, sx[i]=arr[i].sx, fx[i]=arr[i].fx;
    }
    int f(int x){
        if(par[x]==-1) return x;
        par[x]=f(par[x]);
        return par[x];
    }
    void u(int x, int y){
        x=f(x), y=f(y);
        ll s=min(sx[x],sx[y]), f=max(fx[x],fx[y]);
        if(h[x]<h[y]) par[y]=x, sx[x]=s, fx[x]=f;
        else par[x]=y, sx[y]=s, fx[y]=f;
    }
    ll get_h(int x){return h[f(x)];}
    ll get_sx(int x){return sx[f(x)];}
    ll get_fx(int x){return fx[f(x)];}
};

struct Node{
    vector<P> val;
    Node(){}
    Node& operator=(const Node &rhs){
        val.resize(0);
        for(P x : rhs.val) val.push_back(x);
        return *this;
    }
    Node operator+(const Node &rhs) const{
        Node ret;
        int i=0, j=0, sz0=val.size(), sz1=rhs.val.size(), cur=0;
        ret.val.resize(sz0+sz1);
        for(i=0, j=0 ; i<sz0 && j<sz1 ;){
            if(val[i].first<=rhs.val[j].first) ret.val[cur++]=val[i++];
            else ret.val[cur++]=rhs.val[j++];
        }
        for(i ; i<sz0 ; i++) ret.val[cur++]=val[i];
        for(j ; j<sz1 ; j++) ret.val[cur++]=rhs.val[j];
        return ret;
    }
};

struct Q{
    ll sx, fx, v;
    Q(){}
    Q(ll a, ll b, ll c) : sx(a), fx(b), v(c) {}
};

struct SegTree{
    vector<ll> tree, lazy;
    vector<int> idx;
    int base;
    SegTree(int a){
        base=1;
        while(base<a) base<<=1;
        tree.resize(base*2);
        lazy.resize(base*2);
        idx.resize(base*2);
        base--;
        for(int i=1 ; i<=a ; i++) idx[base+i]=i;
        for(int i=base ; i>=1 ; i--) idx[i]=max(idx[i*2],idx[i*2+1]);
    }
    void propagate(int num){
        if(lazy[num]!=0){
            if(num<=base){
                lazy[num*2]+=lazy[num];
                lazy[num*2+1]+=lazy[num];
            }
            tree[num]+=lazy[num]; lazy[num]=0;
        }
    }
    void update(ll val, int st, int fn, int ns=1, int nf=-1, int num=1){
        if(nf==-1) nf=base+1;
        propagate(num);
        if(fn<ns || nf<st) return;
        if(st<=ns && nf<=fn){
            lazy[num]+=val; propagate(num);
            return;
        }
        int mid=(ns+nf)>>1;
        update(val,st,fn,ns,mid,num*2);
        update(val,st,fn,mid+1,nf,num*2+1);
        tree[num]=max(tree[num*2],tree[num*2+1]);
        if(tree[num]==tree[num*2]) idx[num]=idx[num*2];
        else idx[num]=idx[num*2+1];
    }
    ll get_val(){ return tree[1]; }
    int get_idx(){ return idx[1]; }
};

bool cmp1(const A &lhs, const A &rhs){
    return lhs.h>rhs.h;
}

bool cmp2(const Q &lhs, const Q &rhs){
    return lhs.sx<rhs.sx;
}

int n, k, n2, bs, sz, num[300005];
ll m[300005][2], xv[150005];
A flr[150005];
bool fcheck[150005], used[300005];
vector<Q> qry;
vector<Node> mtree;

void del_qry(int num, int idx, SegTree &T)
{
    int sz=mtree[num].val.size();
    for(int i=sz-1 ; i>=0 ; i--){
        int c=mtree[num].val[i].first;
        int j=mtree[num].val[i].second;
        if(c>=idx){
            if(!used[j]) T.update(-qry[j].v,qry[j].sx,qry[j].fx), used[j]=true;
            sz--;
        }
        else break;
    }
    mtree[num].val.resize(sz);
}
    
void solve(int idx, SegTree &T){
    int st=bs+1, fn=bs+num[idx];
    while(st<fn){
        if(st&1){
            del_qry(st,idx,T);
            st++;
        }
        if(!(fn&1)){
            del_qry(fn,idx,T);
            fn--;
        }
        st>>=1, fn>>=1;
    }
    if(st==fn) del_qry(st,idx,T);
}

int main()
{
    scanf("%d",&n);
    for(int i=1 ; i<=n ; i++){
        scanf("%lld %lld",&m[i][0],&m[i][1]);
        if(i>1 && i&1){
            n2++;
            flr[n2]=A(n2,n2,m[i][1]);
            xv[n2+1]=m[i][0];
        }
    }
    scanf("%d",&k);
    
    uf uT(n2,flr);
    sort(flr+1,flr+1+n2,cmp1);
    for(int i=1 ; i<=n2 ; i++){
        A val=flr[i];
        if(val.sx>1 && fcheck[val.sx-1]){
            A ret(uT.get_sx(val.sx-1),uT.get_fx(val.sx-1),uT.get_h(val.sx-1));
            if(val.h!=ret.h) qry.emplace_back(ret.sx,ret.fx,(xv[ret.fx+1]-xv[ret.sx])*(ret.h-val.h));
            uT.u(val.sx-1,val.sx);
        }
        if(val.fx+1<=n2 && fcheck[val.fx+1]){
            A ret(uT.get_sx(val.fx+1),uT.get_fx(val.fx+1),uT.get_h(val.fx+1));
            if(val.h!=ret.h) qry.emplace_back(ret.sx,ret.fx,(xv[ret.fx+1]-xv[ret.sx])*(ret.h-val.h));
            uT.u(val.fx+1,val.sx);
        }
        fcheck[val.sx]=true;
    }
    if(flr[n2].h!=0) qry.emplace_back(1,n2,xv[n2+1]*flr[n2].h);
    
    sort(qry.begin(),qry.end(),cmp2);
    sz=qry.size();
    for(int i=1, j=0 ; i<=n2 ; i++){
        while(j<sz && qry[j].sx<=i) j++;
        num[i]=j;
    }
    
    bs=1;
    while(bs<sz) bs<<=1;
    mtree.resize(bs*2); bs--;
    for(int i=0 ; i<sz ; i++) mtree[bs+i+1].val.push_back(P(qry[i].fx,i));
    for(int i=bs ; i>=1 ; i--) mtree[i]=mtree[i*2]+mtree[i*2+1];
    
    SegTree T(n2);
    for(Q x : qry) T.update(x.v,x.sx,x.fx);
    ll ans=0;
    for(int i=1 ; i<=k ; i++){
        ll maxv=T.get_val();
        int idx=T.get_idx();
        if(maxv==0) break;
        ans+=maxv;
        solve(idx,T);
    }
    printf("%lld",ans);
    return 0;
}

Compilation message

aqua3.cpp: In member function 'Node Node::operator+(const Node&) const':
aqua3.cpp:55:13: warning: statement has no effect [-Wunused-value]
   55 |         for(i ; i<sz0 ; i++) ret.val[cur++]=val[i];
      |             ^
aqua3.cpp:56:13: warning: statement has no effect [-Wunused-value]
   56 |         for(j ; j<sz1 ; j++) ret.val[cur++]=rhs.val[j];
      |             ^
aqua3.cpp: In function 'int main()':
aqua3.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  157 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
aqua3.cpp:159:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  159 |         scanf("%lld %lld",&m[i][0],&m[i][1]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
aqua3.cpp:166:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  166 |     scanf("%d",&k);
      |     ~~~~~^~~~~~~~~

Subtask #1
18.0 / 18.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 4 ms 1132 KB Output is correct
3 Correct 4 ms 1260 KB Output is correct
4 Correct 4 ms 1260 KB Output is correct
5 Correct 4 ms 1260 KB Output is correct
6 Correct 5 ms 1516 KB Output is correct
7 Correct 4 ms 1132 KB Output is correct
8 Correct 3 ms 1132 KB Output is correct
9 Correct 5 ms 1516 KB Output is correct
10 Correct 5 ms 1516 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 59092 KB Output is correct
2 Correct 233 ms 58984 KB Output is correct
3 Correct 214 ms 59856 KB Output is correct
4 Correct 217 ms 59860 KB Output is correct
5 Correct 214 ms 59984 KB Output is correct
6 Correct 429 ms 78620 KB Output is correct
7 Correct 191 ms 54096 KB Output is correct
8 Correct 186 ms 54096 KB Output is correct
9 Correct 290 ms 78536 KB Output is correct
10 Correct 289 ms 78532 KB Output is correct
11 Correct 425 ms 78600 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 59092 KB Output is correct
2 Correct 230 ms 59128 KB Output is correct
3 Correct 222 ms 59988 KB Output is correct
4 Correct 214 ms 59988 KB Output is correct
5 Correct 215 ms 60060 KB Output is correct
6 Correct 427 ms 78768 KB Output is correct
7 Correct 185 ms 54228 KB Output is correct
8 Correct 186 ms 54100 KB Output is correct
9 Correct 307 ms 78672 KB Output is correct
10 Correct 290 ms 78536 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 59212 KB Output is correct
2 Correct 376 ms 59348 KB Output is correct
3 Correct 304 ms 59984 KB Output is correct
4 Correct 314 ms 59860 KB Output is correct
5 Correct 278 ms 59988 KB Output is correct
6 Correct 215 ms 53968 KB Output is correct
7 Correct 210 ms 54096 KB Output is correct
8 Correct 391 ms 78664 KB Output is correct
9 Correct 445 ms 78664 KB Output is correct