Submission #29277

#	Time	Username	Problem	Language	Result	Execution time	Memory
29277		TAMREF	수족관 3 (KOI13_aqua3)	C++11	100 / 100	359 ms	47224 KiB

aqua3

#include <bits/stdc++.h>
using namespace std;
const int mx=300005;
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;
    inline bool operator< (Node z){
        return y2<z.y2;
    }
} node[mx];

map<int,int> itv;
map<int,int>::iterator it;
vector<int> G[mx];
int arr[mx], arr_top;
int Q[mx], q_f, q_r;
int Bfs[mx], br;
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]){
            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;
        }
    }
    ver[0].y=ver[V+1].y=-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 && 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(max_y==ver[L].y) ver[L].ri=max(ver[L].ri,R);
        if(max_y==ver[R].y) ver[R].le=min(ver[R].le,L);
        ver[n].up_y=max_y;
        //printf("N - ver[%d] : Lx=%d, Rx=%d, L=%d, R=%d, y=%d, upy=%d\n",n,ver[n].a,ver[n].b,ver[n].le,ver[n].ri,ver[n].y,ver[n].up_y);
        //printf("L - ver[%d] : Lx=%d, Rx=%d, L=%d, R=%d, y=%d, upy=%d\n",L,ver[L].a,ver[L].b,ver[L].le,ver[L].ri,ver[L].y,ver[L].up_y);
        //printf("R - ver[%d] : Lx=%d, Rx=%d, L=%d, R=%d, y=%d, upy=%d\n",R,ver[R].a,ver[R].b,ver[R].le,ver[R].ri,ver[R].y,ver[R].up_y);
    }
    M=1;
    for(i=1;i<=V;i++){
        if(ver[i].up_y==ver[i].y) continue;
        ++M;
        L=ver[i].le, R=ver[i].ri;
        node[M].l=(L>0?ver[L].b:0);
        node[M].r=(R<=V?ver[R].a:X[N]);
        node[M].w= 1LL*(node[M].r-node[M].l)*(ver[i].y-ver[i].up_y);
        node[M].y2=ver[i].y;
    }
    sort(node+2,node+M+1);
    for(i=M;i>=2;--i){
        arr_top=0;
        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[arr_top++]=it->first;
            G[i].push_back(k);
        }
        for(j=0;j<arr_top;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[q_r++]=1;q_f!=q_r;){
        q=Q[q_f++];
        Bfs[br++]=q;
        for(i=G[q].size();i--;) Q[q_r++]=G[q][i];
    }
    for(i=M;i--;){
        n=Bfs[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];
            }
        }
        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:39:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
                   ^
aqua3.cpp:40: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:41: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: 21 / 21
• Subtask 4: 15 / 15
• Subtask 5: 16 / 16