#include <stdio.h>
#include <algorithm>
using namespace std;
int n,k;
struct data{
int x,y;
bool hole;
}a[300002];
struct data2{
int first,second;
bool operator()(data2 x,data2 y){
if(x.first != y.first) return (x.first < y.first);
return (x.second < y.second);
}
}ta[150002];
int find_hole(int ix,int iy){
int s,mid,e;
s = 1;
e = (n/2)-1;
while(true){
mid = (s+e)/2;
if(a[mid*2].x == ix && a[mid*2].y == iy) return mid*2;
if(a[mid*2].x > ix) e = mid-1;
else s = mid+1;
}
}
int left_node[150002],right_node[150002];
int left_y[150002],right_y[150002];
void Input(){
int i,ix,iy;
//freopen("input.txt","r",stdin);
scanf("%d",&n);
for(i=1; i<=n; i++){
scanf("%d %d",&a[i].x,&a[i].y);
a[i].hole = false;
}
scanf("%d",&k);
for(i=1; i<=k; i++){
scanf("%d %d",&ix,&iy);
a[find_hole(ix,iy)].hole = true;
scanf("%d %d",&ix,&iy);
}
for(i=1; i<n/2; i++) ta[i].first = a[i*2].y;
for(i=1; i<n/2; i++) ta[i].second = i*2;
sort(ta+1,ta+(n/2),data2());
}
void set_tree(){
int i,index;
int l,r;
for(i=1; i<n/2; i++){
left_node[i] = i-1;
right_node[i] = i+1;
left_y[i] = a[(i*2)-1].y;
right_y[i] = a[(i*2)+2].y;
}
for(i=(n/2)-1; i>=1; i--){
index = ta[i].second/2;
if(left_y[index] >= right_y[index]){
l = left_node[index];
right_node[l] = right_node[index];
right_y[l] = right_y[index];
}else{
r = right_node[index];
left_node[r] = left_node[index];
left_y[r] = left_y[index];
}
}
}
int hole[150002];
double watertime[150002];
long long leftwater;
long long water;
void aqua(){
int i,index;
for(i=(n/2)-1; i>=1; i--){
index = ta[i].second/2;
if(a[index*2].hole == true) hole[index]++;
hole[right_node[index]] += hole[index];
hole[left_node[index]] += hole[index];
water = a[right_node[index]*2].x - a[(left_node[index]*2)+1].x;
if(left_y[index] >= right_y[index]){
water *= (long long)(a[index*2].y-a[left_node[index]*2].y);
}else{
water *= (long long)(a[index*2].y-a[right_node[index]*2].y);
}
if(hole[index] == 0) leftwater += water;
else watertime[index] += ((double)water / (double) hole[index]);
watertime[left_node[index]] = max(watertime[left_node[index]],watertime[index]);
watertime[right_node[index]] = max(watertime[right_node[index]],watertime[index]);
}
}
void print(){
printf("%.2f\n",watertime[ta[1].second/2]);
printf("%lld",leftwater);
}
int main(void){
Input();
set_tree();
aqua();
print();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
9872 KB |
Output is correct |
| 2 |
Correct |
0 ms |
9872 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
9872 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
9872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
9872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
168 ms |
9872 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
