Submission #4459

#TimeUsernameProblemLanguageResultExecution timeMemory
4459model_code수족관 1 (KOI13_aqua1)C++98
100 / 100
4 ms1288 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...