Submission #4465

#	Time	Username	Problem	Language	Result	Execution time	Memory
4465		model_code	수족관 2 (KOI13_aqua2)	C++98	100 / 100	200 ms	19840 KiB

aqua2

#include <stdio.h>
#include <algorithm>
#define Max_N 300005
#define Max(a,b) ((a)>(b)?(a):(b))
FILE *in  = stdin;
FILE *out = stdout;

int E, N, K, i;
int input_x[Max_N]  , input_y[Max_N];
int left_node[Max_N], right_node[Max_N], x[Max_N]     , y[Max_N];
int left_x[Max_N]   , right_x[Max_N]   , left_y[Max_N], right_y[Max_N];
int hole[Max_N];
long long ans_remain;
double Time[Max_N], ans_time;

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);
	for(i=0; i<E; i++) fscanf(in, "%d%d", &input_x[i], &input_y[i]);
}

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

int find_hole_num(int hole_x){
	int l = 0, r = N-1;
	while(l <= r){
		int mid = (l+r) / 2;
		if(x[mid]  > hole_x) r = mid - 1;
		if(x[mid]  < hole_x) l = mid + 1;
		if(x[mid] == hole_x) return mid;
	}
}

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; i++){
		int index = line[i].index;
		if(left_y[index] >= right_y[index] && left_node[index] < N){
			long long area = (long long)(y[index] - left_y[index]) * (long long)(right_x[index] - left_x[index]);
						
			if(hole[index] != 0) Time[index] += area * 1.0 / hole[index];				
			else ans_remain += area;

			int l = left_node[index];
			Time[l] = Max(Time[l], Time[index]);
			right_node[l] = right_node[index]; right_x[l] = right_x[index]; right_y[l] = right_y[index];
			hole[l] += hole[index];
		}
		else{
			long long area = (long long)(y[index] - right_y[index]) * (long long)(right_x[index] - left_x[index]);

			if(hole[index] != 0) Time[index] += area * 1.0 / hole[index];
			else ans_remain += area;

			int r = right_node[index];
			Time[r] = Max(Time[r], Time[index]);
			left_node[r] = left_node[index]; left_x[r] = left_x[index]; left_y[r] = left_y[index];
			hole[r] += hole[index];
		}
	}
}

void output(){
	for(i=0; i<N; i++) if(Time[i] > ans_time) ans_time = Time[i];
	fprintf(out, "%.2lf\n%lld", ans_time, ans_remain);
}

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

• Subtask 1: 13 / 13
• Subtask 2: 21 / 21
• Subtask 3: 35 / 35
• Subtask 4: 31 / 31