oj.uz

답안 #4927

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4927 2014-01-15T04:27:36 Z Qwaz 수족관 3 (KOI13_aqua3) C++
100 / 100
 164 ms 28704 KB 
#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.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12492 KB Output is correct
2 Correct 0 ms 12492 KB Output is correct
3 Correct 0 ms 12492 KB Output is correct
4 Correct 0 ms 12492 KB Output is correct
5 Correct 0 ms 12492 KB Output is correct
6 Correct 0 ms 12492 KB Output is correct
7 Correct 0 ms 12492 KB Output is correct
8 Correct 0 ms 12492 KB Output is correct
9 Correct 0 ms 12492 KB Output is correct
10 Correct 0 ms 12492 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 12492 KB Output is correct
2 Correct 4 ms 12492 KB Output is correct
3 Correct 0 ms 12492 KB Output is correct
4 Correct 0 ms 12492 KB Output is correct
5 Correct 0 ms 12492 KB Output is correct
6 Correct 0 ms 12556 KB Output is correct
7 Correct 4 ms 12492 KB Output is correct
8 Correct 4 ms 12492 KB Output is correct
9 Correct 4 ms 12492 KB Output is correct
10 Correct 4 ms 12492 KB Output is correct

Subtask #3
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 16080 KB Output is correct
2 Correct 164 ms 16080 KB Output is correct
3 Correct 140 ms 17128 KB Output is correct
4 Correct 144 ms 17136 KB Output is correct
5 Correct 128 ms 17132 KB Output is correct
6 Correct 136 ms 28704 KB Output is correct
7 Correct 124 ms 16084 KB Output is correct
8 Correct 108 ms 16084 KB Output is correct
9 Correct 148 ms 18692 KB Output is correct
10 Correct 164 ms 18688 KB Output is correct
11 Correct 116 ms 28704 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 16080 KB Output is correct
2 Correct 148 ms 16080 KB Output is correct
3 Correct 136 ms 17128 KB Output is correct
4 Correct 136 ms 17136 KB Output is correct
5 Correct 144 ms 17140 KB Output is correct
6 Correct 128 ms 28704 KB Output is correct
7 Correct 120 ms 16084 KB Output is correct
8 Correct 108 ms 16084 KB Output is correct
9 Correct 160 ms 18688 KB Output is correct
10 Correct 152 ms 18692 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 112 ms 16080 KB Output is correct
2 Correct 96 ms 16080 KB Output is correct
3 Correct 120 ms 17132 KB Output is correct
4 Correct 100 ms 17132 KB Output is correct
5 Correct 128 ms 17140 KB Output is correct
6 Correct 124 ms 16084 KB Output is correct
7 Correct 116 ms 16084 KB Output is correct
8 Correct 144 ms 18692 KB Output is correct
9 Correct 128 ms 18696 KB Output is correct