Submission #4459

#	Time	Username	Problem	Language	Result	Execution time	Memory
4459		model_code	수족관 1 (KOI13_aqua1)	C++98	100 / 100	4 ms	1288 KiB

aqua1

#include <stdio.h>
#include <algorithm>
#define Max_N 5005
FILE *in  = stdin;
FILE *out = stdout;

int E, N, K, i, j;
int input_x[Max_N], input_y[Max_N];
int left_x[Max_N], right_x[Max_N], x[Max_N], y[Max_N];
int hole[Max_N], ans_remain;

struct Line{
	int x, y, index;
	bool operator()(Line c, Line d){
		if(c.y != d.y) return (c.y > d.y);
		else return (c.x < d.x);
	}
}line[Max_N];

void input(){
	fscanf(in, "%d", &E);
	input_x[0] = -1; input_y[0] = -1; input_x[1] = -1; input_y[1] =  0;
	for(i=2; i<E+2; i++) fscanf(in, "%d%d", &input_x[i], &input_y[i]); E+=2;
	input_x[E] = input_x[E-1]+1; input_y[E++] = 0; input_x[E] = input_x[E-1]; input_y[E++] = -1;
}

void make_line(){
	for(i=1; i<E-1; i+=2){
		left_x[N] = input_x[i]; right_x[N] = input_x[i+1]; x[N] = input_x[i]; y[N] = input_y[i];
		line[N].index = N; line[N].x=input_x[i]; line[N++].y = input_y[i];
	}
	std::sort(line, line+N,	Line());
}

int find_hole_num(int hole_x){
	for(int i=0; i<N; i++){
		if(x[i] == hole_x) return i;
	}	
}

void arrange_hole(){
	fscanf(in, "%d", &K);
	for(i=0; i<K; i++){
		int hole_x1, hole_y1, hole_x2, hole_y2;
		fscanf(in, "%d %d %d %d", &hole_x1, &hole_y1, &hole_x2, &hole_y2);
		int hole_num = find_hole_num(hole_x1);
		hole[hole_num] ++;
	}
}

void process(){
	for(i=0; i<N-2; i++){
		int index = line[i].index, l=-1, r=-1;		

		for(j=index-1; j>=0; j--){
			if(y[j] < y[index]){l=j; break;}
		}
		for(j=index+1; j<N; j++){
			if(y[j] <= y[index]){r=j; break;}
		}
		
		if(y[l] > y[r]){
			int area = (y[index] - y[l]) * (left_x[r] - right_x[l]);
			if(hole[index] == 0) ans_remain += area;
			
			hole[l] += hole[index];
		}
		else{
			int area = (y[index] - y[r]) * (left_x[r] - right_x[l]);
			if(hole[index] == 0) ans_remain += area;

			hole[r] += hole[index];
		}
	}
}

void output(){
	fprintf(out, "%d", ans_remain);
}

int main(){
	input();		
	make_line();
	arrange_hole();
	process();
	output();	
	return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 22 / 22
• Subtask 4: 36 / 36