| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4465 |
2013-10-07T15:24:01 Z |
model_code |
수족관 2 (KOI13_aqua2) |
C++ |
|
200 ms |
19840 KB |
#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 6 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 8 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 9 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 10 |
Correct |
0 ms |
19840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 6 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 8 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 9 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 10 |
Correct |
0 ms |
19840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 6 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 8 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 9 |
Correct |
0 ms |
19840 KB |
Output is correct |
| 10 |
Correct |
0 ms |
19840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
192 ms |
19840 KB |
Output is correct |
| 2 |
Correct |
168 ms |
19840 KB |
Output is correct |
| 3 |
Correct |
196 ms |
19840 KB |
Output is correct |
| 4 |
Correct |
168 ms |
19840 KB |
Output is correct |
| 5 |
Correct |
172 ms |
19840 KB |
Output is correct |
| 6 |
Correct |
128 ms |
19840 KB |
Output is correct |
| 7 |
Correct |
192 ms |
19840 KB |
Output is correct |
| 8 |
Correct |
120 ms |
19840 KB |
Output is correct |
| 9 |
Correct |
200 ms |
19840 KB |
Output is correct |
| 10 |
Correct |
168 ms |
19840 KB |
Output is correct |
