oj.uz

Submission #29190

# Submission time Handle Problem Language Result Execution time Memory
29190 2017-07-18T15:28:36 Z TAMREF 수족관 3 (KOI13_aqua3) C++11
100 / 100
 389 ms 44736 KB 
#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;
    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

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.0 / 18.0

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

Subtask #2
30.0 / 30.0

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

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 366 ms 39940 KB Output is correct
2 Correct 343 ms 39940 KB Output is correct
3 Correct 233 ms 39848 KB Output is correct
4 Correct 266 ms 39816 KB Output is correct
5 Correct 249 ms 39848 KB Output is correct
6 Correct 199 ms 44736 KB Output is correct
7 Correct 139 ms 39596 KB Output is correct
8 Correct 173 ms 39596 KB Output is correct
9 Correct 353 ms 43844 KB Output is correct
10 Correct 366 ms 43844 KB Output is correct
11 Correct 209 ms 44736 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 39940 KB Output is correct
2 Correct 333 ms 39940 KB Output is correct
3 Correct 243 ms 39816 KB Output is correct
4 Correct 169 ms 39816 KB Output is correct
5 Correct 273 ms 39816 KB Output is correct
6 Correct 233 ms 44736 KB Output is correct
7 Correct 186 ms 39596 KB Output is correct
8 Correct 166 ms 39596 KB Output is correct
9 Correct 379 ms 43844 KB Output is correct
10 Correct 373 ms 43844 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 39940 KB Output is correct
2 Correct 339 ms 39940 KB Output is correct
3 Correct 249 ms 39848 KB Output is correct
4 Correct 223 ms 39848 KB Output is correct
5 Correct 269 ms 40368 KB Output is correct
6 Correct 143 ms 39596 KB Output is correct
7 Correct 166 ms 39596 KB Output is correct
8 Correct 359 ms 43844 KB Output is correct
9 Correct 359 ms 43844 KB Output is correct