| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4459 |
2013-10-07T05:20:02 Z |
model_code |
수족관 1 (KOI13_aqua1) |
C++ |
|
4 ms |
1288 KB |
#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 time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1288 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 3 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 4 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 5 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 7 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 8 |
Correct |
4 ms |
1288 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1288 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1288 KB |
Output is correct |
