Submission #4927

#	Time	Username	Problem	Language	Result	Execution time	Memory
4927		Qwaz	수족관 3 (KOI13_aqua3)	C++98	100 / 100	164 ms	28704 KiB

aqua3

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;
typedef pair < ll, int > pli;
const int MAX=150020;

struct line {
	int l, r, y;
};

int n, k, dFull, xMax;
line data[MAX];

void input(){
	scanf("%d", &n);

	int i, lastX, lastY;
	scanf("%d%d", &lastX, &lastY);
	for(i=1; i<n; i++){
		int nx, ny;
		scanf("%d%d", &nx, &ny);
		if(ny == lastY){
			data[dFull].l = lastX;
			data[dFull].r = nx;
			data[dFull].y = ny;
			dFull++;
		}
		lastX = nx;
		lastY = ny;
	}
	xMax = lastX;

	scanf("%d", &k);
}

vector < int > to[MAX];
int cnt[MAX], p[MAX], pos[MAX];
ll size[MAX], all;

int l[MAX], r[MAX], y[MAX], stack[MAX], top, renum[MAX], rFull;

void init(){
	int i;
	top = 0;
	for(i=0; i<dFull; i++){
		while(top && data[stack[top-1]].y > data[i].y) top--;

		if(top && data[stack[top-1]].y == data[i].y){
			renum[i] = renum[stack[top-1]];
			stack[top-1] = i;
		} else {
			renum[i] = rFull++;

			y[renum[i]] = data[i].y;
			p[renum[i]] = -1;
			if(top){
				l[renum[i]] = data[stack[top-1]].r;
				p[renum[i]] = renum[stack[top-1]];
			}

			stack[top++] = i;
		}
	}

	top = 0;
	for(i=dFull-1; i>=0; i--){
		while(top && data[stack[top-1]].y > data[i].y) top--;

		if(top && data[stack[top-1]].y == data[i].y)
			stack[top-1] = i;
		else {
			if(top){
				r[renum[i]] = data[stack[top-1]].l;
				if(p[renum[i]] == -1 || y[p[renum[i]]] < y[renum[stack[top-1]]])
					p[renum[i]] = renum[stack[top-1]];
			} else
				r[renum[i]] = xMax;

			stack[top++] = i;
		}
	}

	for(i=0; i<rFull; i++){
		size[i] = (ll)(r[i]-l[i])*(p[i] == -1 ? y[i] : y[i]-y[p[i]]);

		if(p[i] != -1){
			cnt[p[i]]++;
			pos[i] = to[p[i]].size();
			to[p[i]].push_back(i);
		}

		all += size[i];
	}
}

priority_queue < pli > pq;
bool deleted[MAX];

void deflate(int from, int first=-1){
	if(deleted[from] || from == -1 || cnt[from] != 1) return;

	deflate(p[from], from);

	int next = first;
	if(next == -1){
		int i;
		for(i=0; i<to[from].size(); i++){
			int t = to[from][i];
			if(!deleted[t]){
				next = t;
				break;
			}
		}
	}

	p[next] = p[from];
	pos[next] = pos[from];
	size[next] += size[from];
	if(p[from] != -1)
		to[p[from]][pos[from]] = next;
	deleted[from] = 1;

	if(to[next].size() == 0)
		pq.push(pli(-size[next], next));

	if(first == -1) return deflate(next);
}

void solve(){
	int i, leafCnt=0;
	for(i=0; i<rFull; i++)
		if(to[i].size() == 0){
			leafCnt++;
			if(p[i] != -1) deflate(p[i]);

			pq.push(pli(-size[i], i));
		}

	if(leafCnt <= k){
		printf("%lld\n", all);
		return;
	} else k = leafCnt-k;

	while(k){
		pli now = pq.top();
		pq.pop();
		if(!deleted[now.second] && -now.first == size[now.second]){
			k--;
			deleted[now.second] = 1;

			all += now.first;

			if(p[now.second] != -1){
				cnt[p[now.second]]--;
				deflate(p[now.second]);
			}
		}
	}

	printf("%lld\n", all);
}

int main(){
	input();

	init();
	solve();

	return 0;
}

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