Submission #29189

#	Time	Username	Problem	Language	Result	Execution time	Memory
29189		TAMREF	수족관 3 (KOI13_aqua3)	C++11	48 / 100	19 ms	5408 KiB

aqua3

#include <bits/stdc++.h>
using namespace std;
const int mx=30005;
typedef long long ll;
typedef pair<ll,int> pli;

int N,K,V,M;
ll ans;
int X[mx], Y[mx], order_y[mx], T[mx];
ll D[mx];
bool removed[mx];

struct Vert{
    int y,a,b;
    int up_y;
    int le,ri;
} ver[mx];

struct Node{
    int l,r,y2;
    ll w;
    int mom;
    bool operator< (Node z){
        return y2<z.y2;
    }
} node[mx];

map<int,int> itv;
map<int,int>::iterator it;
vector<int> G[mx], arr, order;
queue<int> Q;
priority_queue<pli> pQ;

int main(){
    int i,j,k,n,q,L,R;
    int max_y;
    scanf("%d",&N);
    for(i=1;i<=N;i++) scanf("%d%d",&X[i],&Y[i]);
    scanf("%d",&K);
    for(i=2;i<N-1;i++){
        if(Y[i]==Y[i+1]){
            ++V;
            ver[V].a=X[i], ver[V].b=X[i+1], ver[V].y=Y[i];
            ver[V].le=V-1, ver[V].ri=V+1;

        }
    }
    for(i=1;i<=V;i++) order_y[i]=i;
    sort(order_y+1,order_y+V+1,[](int u,int v){
            if(ver[u].y==ver[v].y) return ver[u].a>ver[v].a;
            return ver[u].y>ver[v].y;
         });
    for(i=1;i<=V;i++){
        n=order_y[i];
        k=0;
        max_y=0;
        L=ver[n].le, R=ver[n].ri;
        if(L>0&&ver[L].y<=ver[n].y)
            max_y=max(max_y,ver[L].y);
        if(R<=V&&ver[R].y<=ver[n].y){
            max_y=max(max_y,ver[R].y);
        }
        if(L>0&&max_y==ver[L].y){
            ver[L].le=min(ver[L].le,L);
            ver[L].ri=max(ver[L].ri,R);
        }
        if(R<=V&&max_y==ver[R].y){
            ver[R].le=min(ver[R].le,L);
            ver[R].ri=max(ver[R].ri,R);
        }
        ver[n].up_y=max_y;
        //printf("ver[%d] : Lx=%d, Rx=%d, L=%d, R=%d, y=%d, upy=%d\n",n,ver[n].a,ver[n].b,L,R,ver[n].y,ver[n].up_y);
    }
    M=1;
    for(i=1;i<=V;i++){
        L=ver[i].le, R=ver[i].ri;
        int Lx=(L>0?ver[L].b:0);
        int Rx=(R<=V?ver[R].a:X[N]);
        ll sz = 1LL*(Rx-Lx)*(ver[i].y-ver[i].up_y);
        //printf("node %d : Lx=%d, Rx=%d, y=%d, upy=%d, sz=%lld\n",M,Lx,Rx,ver[i].y,ver[i].up_y,sz);
        if(ver[i].up_y == ver[i].y) continue;
        ++M;
        node[M].y2=ver[i].y;
        node[M].l=Lx, node[M].r=Rx;
        node[M].w=sz;
    }
    sort(node+2,node+M+1);
    for(i=M;i>=2;--i){
        arr.clear();
        for(it = itv.upper_bound(node[i].l);it!=itv.end();++it){
            if(it->first > node[i].r) break;
            k = it->second;
            node[k].mom=i;
            arr.push_back(it->first);
            G[i].push_back(k);
        }
        for(j=0;j<arr.size();j++) itv.erase(arr[j]);
        itv[node[i].r]=i;
    }
    for(i=2;i<=M;i++){
        if(!node[i].mom){
            node[i].mom=1;
            G[1].push_back(i);
        }
    }
    for(Q.push(1);!Q.empty();){
        q=Q.front(); Q.pop();
        order.push_back(q);
        for(i=G[q].size();i--;) Q.push(G[q][i]);
    }
    for(i=M;i--;){
        n=order[i];
        D[n]=node[n].w; T[n]=n;
        for(j=G[n].size();j--;){
            k=G[n][j];
            if(D[n]<D[k]+node[n].w){
                D[n]=D[k]+node[n].w;
                T[n]=T[k];
            }
        }
        //printf("D[%d]=%lld\n",n,D[n]);
        pQ.push(pli(D[n],n));
    }
    while(K--){
        while(!pQ.empty() && removed[pQ.top().second]) pQ.pop();
        if(pQ.empty()) break;
        k=pQ.top().second; pQ.pop();
        ans+=D[k];
        for(k=T[k];k&&!removed[k];k=node[k].mom)
            removed[k]=1;
    }
    printf("%lld\n",ans);
    return 0;
}

Compilation message (stderr)

aqua3.cpp: In function 'int main()':
aqua3.cpp:97:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<arr.size();j++) itv.erase(arr[j]);
                  ^
aqua3.cpp:37:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
aqua3.cpp:38:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(i=1;i<=N;i++) scanf("%d%d",&X[i],&Y[i]);
                                                ^
aqua3.cpp:39:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&K);
                   ^

• Subtask 1: 18 / 18
• Subtask 2: 30 / 30
• Subtask 3: 0 / 21
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16