#include <stdio.h>
#include <stdlib.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;
}
}
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()); // n*n(???)
}
int left_node[150002],right_node[150002];
int left_y[150002],right_y[150002],ttt[150002];
void set_tree(){
int i,index;
int l,r;
for(i=(n/2)-1; i>=1; i--){
ttt[ta[i].second/2] = i;
}
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>=2; i--){
index = ta[i].second/2;
if(left_y[index] >= right_y[index] && left_node[index] < (n/2)){
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 before[150002],next[150002];
int wleft[150002],wright[150002];
void set_tree2(){
int i,index;
for(i=1; i<n/2; i++){
left_y[i] = right_y[i] = 999999999;
index = ta[i].second/2;
before[i] = ttt[left_node[index]];
next[i] = ttt[right_node[index]];
}
for(i=1; i<n/2; i++){
if(before[i] != 0 && right_y[before[i]] > a[ta[i].second].y){
wright[before[i]] = i;
right_y[before[i]] = a[ta[i].second].y;
}
if(next[i] != 0 && left_y[next[i]] > a[ta[i].second].y){
wleft[next[i]] = i;
left_y[next[i]] = a[ta[i].second].y;
}
}
}
double watertime;
long long leftwater;
pair<int,double> tmp;
int dx,dy;
double rtime;
long long water;
pair<int,double> aqua(int x){
int hole;
double ltime;
hole = 0;
if(a[ta[x].second].hole == true) hole++;
ltime = rtime = 0;
if(wleft[x] != 0){
tmp = aqua(wleft[x]);
hole += tmp.first;
ltime = tmp.second;
}
if(wright[x] != 0){
tmp = aqua(wright[x]);
hole += tmp.first;
rtime = tmp.second;
}
if(next[x] == 0) dx = a[n].x;
else dx = a[ta[next[x]].second].x;
if(before[x] != 0) dx -= a[ta[before[x]].second+1].x;
dy = a[ta[x].second].y - max(a[ta[before[x]].second].y,a[ta[next[x]].second].y);
water = (long long)dx * (long long)dy;
if(hole == 0){
leftwater += water;
return make_pair(0,0);
}
return make_pair(hole,max(ltime,rtime) + ((double)water / (double)hole));
}
void print(){
printf("%.2f\n",watertime);
printf("%lld",leftwater);
}
int main(void){
Input();
set_tree();
set_tree2();
tmp = aqua(1);
watertime = tmp.second;
print();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 3 |
Memory limit exceeded |
35 ms |
131072 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 3 |
Memory limit exceeded |
40 ms |
131072 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 2 |
Correct |
0 ms |
11044 KB |
Output is correct |
| 3 |
Memory limit exceeded |
29 ms |
131072 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
205 ms |
11044 KB |
Output is correct |
| 2 |
Correct |
141 ms |
11044 KB |
Output is correct |
| 3 |
Memory limit exceeded |
198 ms |
131072 KB |
Memory limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
