Submission #4481

#	Time	Username	Problem	Language	Result	Execution time	Memory
4481		model_code	수족관 3 (KOI13_aqua3)	C++98	100 / 100	380 ms	43876 KiB

aqua3

#include <stdio.h>
#include <map>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define MAXN 300005
typedef long long lld;
typedef pair<lld,int> pli;

/*
V = 수평 선분의 개수
M = 트리에서 노드 개수
*/
int N,K,V,M; lld ans;
int X[MAXN],Y[MAXN],order_y[MAXN];
lld D[MAXN]; int T[MAXN]; bool removed[MAXN];

struct VERTICAL{ // 수평선분 정보
	int y,a,b; // y좌표, 왼쪽 x좌표, 오른쪽 x좌표
	int up_y; // 자신의 바로 위 y좌표
	int left,right; // 왼쪽 선분 번호, 오른쪽 선분 번호
} ver[MAXN];

struct NODE{ // 트리의 노드 정보
	int y1,y2,l,r; // 노드가 의미하는 범위의 위,아래 y좌표, 왼쪽 x좌표, 오른쪽 x좌표
	lld w; // 노드의 가중치
	int mom; // 부모 노드의 노드 번호
	bool operator < (const NODE &ot)const{
		return y2<ot.y2;
	}
} node[MAXN];

map <int,int> interval;
map <int,int>::iterator it;
vector <int> con[MAXN],arr,order;
queue <int> que;
priority_queue <pli> pque;

bool cmp(int a,int b){ return ver[a].y!=ver[b].y?ver[a].y>ver[b].y:ver[a].a>ver[b].a; }

int main()
{
	int i,j,k,n,q;
	int max_y;
	scanf("%d",&N);
	for (i=1;i<=N;i++) scanf("%d%d",X+i,Y+i);
	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].left = V-1, ver[V].right = V+1;
	}
	scanf("%d",&K);
	///////////////////////////////////////////////////////////////////////////////////////////////
	/* 트리 만들기 시작 */
	/*
	수평 선분 정보 갱신
	시간복잡도 O(N lg N)
	*/
	for (i=1;i<=V;i++) order_y[i] = i;
	sort(order_y+1,order_y+V+1,cmp);
	for (i=1;i<=V;i++){
		n = order_y[i]; k = 0;

		max_y = 0;
		if (ver[n].left > 0 && ver[ver[n].left].y <= ver[n].y)
			max_y = max(max_y,ver[ver[n].left].y);
		if (ver[n].right <= V && ver[ver[n].right].y <= ver[n].y)
			max_y = max(max_y,ver[ver[n].right].y);

		if (ver[n].left > 0 && max_y == ver[ver[n].left].y){
			ver[ver[n].left].left = min(ver[ver[n].left].left,ver[n].left);
			ver[ver[n].left].right = max(ver[ver[n].left].right,ver[n].right);
		}
		if (ver[n].right <= V && max_y == ver[ver[n].right].y){
			ver[ver[n].right].left = min(ver[ver[n].right].left,ver[n].left);
			ver[ver[n].right].right = max(ver[ver[n].right].right,ver[n].right);
		}
		ver[n].up_y = max_y;
	}
	/*
	트리의 노드 정보 만들기
	시간복잡도 O(N lg N)
	*/
	M = 1; // 가상의 노드(루트)
	for (i=1;i<=V;i++){
		int left=ver[i].left>0?ver[ver[i].left].b:0;
		int right=ver[i].right<=V?ver[ver[i].right].a:X[N];
		lld size=lld(right-left)*(ver[i].y-ver[i].up_y);
		if (ver[i].up_y == ver[i].y) // 겹치는 노드면 노드 추가를 생략
			continue;
		M++;
		node[M].y1 = ver[i].up_y, node[M].y2 = ver[i].y;
		node[M].l = left, node[M].r = right;
		node[M].w = size;
	}
	sort(node+2,node+M+1);
	/*
	간성 정보 만들기
	시간복잡도 O(N lg N)
	*/
	for (i=M;i>1;i--){
		arr.clear();
		for (it=interval.upper_bound(node[i].l);it!=interval.end();++it){
			if (it->first > node[i].r) break;
			k = it->second;
			node[k].mom = i;
			arr.push_back(it->first);
			con[i].push_back(k);
		}
		for (j=0;j<arr.size();j++) interval.erase(arr[j]);
		interval[node[i].r] = i;
	}
	/* 루트와 연결 */
	for (i=2;i<=M;i++){
		if (!node[i].mom) node[i].mom = 1, con[1].push_back(i);
	}
	/* 트리 만들기 끝 */
	///////////////////////////////////////////////////////////////////////////////////////////////

	/* 노드의 탐색 순서 구하기 */
	que.push(1);
	while (!que.empty()){
		q = que.front(); que.pop();
		order.push_back(q);
		for (i=con[q].size();i--;){
			k = con[q][i];
			que.push(k);
		}
	}
	/* 노드의 값 계산 */
	for (i=M;i--;){
		n = order[i];
		D[n] = node[n].w; T[n] = n;
		for (j=con[n].size();j--;){
			k = con[n][j];
			if (D[n] < D[k]+node[n].w)
				D[n] = D[k]+node[n].w,
				T[n] = T[k];
		}
		pque.push(pli(D[n],n));
	}
	/*
	노드의 값을 기준으로 욕심쟁이 기법
	시간복잡도 O(N lg N)
	*/
	while (K--){
		while (!pque.empty() && removed[pque.top().second])
			pque.pop();
		if (pque.empty()) break;
		k = pque.top().second; pque.pop();
		ans += D[k];
		for (k=T[k];k&&!removed[k];k=node[k].mom)
			removed[k] = 1;
	}
	printf("%lld\n",ans);
	return 0;
}

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