#include <stdio.h>
#include <algorithm>
using namespace std;
int n,k;
struct data{
int x,y;
bool hole;
}a[300002];
pair<int,int> ta[150002];
int sa[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 root;
int before[150002],next[150002];
int rb[150002],par[150002];
int left[150002],right[150002];
bool color[150002];
void Left_rotate(int x){
int y = right[x];
right[x] = left[y];
if(left[y] != 0){
par[left[y]] = x;
}
par[y] = par[x];
if(par[x] == 0){
root = y;
}else if(x == left[par[x]]){
left[par[x]] = y;
}else{
right[par[x]] = y;
}
left[y] = x;
par[x] = y;
}
void Right_rotate(int x){
int y = left[x];
left[x] = right[y];
if(right[y] != 0){
par[right[y]] = x;
}
par[y] = par[x];
if(par[x] == 0){
root = y;
}else if(x == right[par[x]]){
right[par[x]] = y;
}else{
left[par[x]] = y;
}
right[y] = x;
par[x] = y;
}
int grand;
void rb_insert(int x){
int y;
color[x] = false;
par[x] = root;
while(true){
if(rb[par[x]] < rb[x] && right[par[x]] == 0){
right[par[x]] = x;
break;
}else if(rb[par[x]] > rb[x] && left[par[x]] == 0){
left[par[x]] = x;
break;
}else if(rb[par[x]] < rb[x]) par[x] = right[par[x]];
else par[x] = left[par[x]];
}
if(color[par[x]] == true) return;
color[0] = true;
grand = par[par[x]];
if(left[grand] == par[x]){
y = right[grand];
if(color[y] == false){
color[grand] = false;
color[par[x]] = color[y] = true;
return;
}
if(right[par[x]] == x){
color[grand] = false;
color[x] = true;
Left_rotate(par[x]);
Right_rotate(grand);
}else{
color[grand] = false;
color[par[x]] = true;
Right_rotate(grand);
}
}else{
y = left[grand];
if(color[y] == false){
color[grand] = false;
color[par[x]] = color[y] = true;
return;
}
if(left[par[x]] == x){
color[grand] = false;
color[x] = true;
Right_rotate(par[x]);
Left_rotate(grand);
}else{
color[grand] = false;
color[par[x]] = true;
Left_rotate(grand);
}
}
}
int find_before(int x){
if(left[x] != 0){
x = left[x];
while(true){
if(right[x] == 0) break;
x = right[x];
}
return x;
}
while(true){
if(par[x] == 0) return 0;
if(x == left[par[x]]){
x = par[x];
}else{
return par[x];
}
}
}
int find_next(int x){
if(right[x] != 0){
x = right[x];
while(true){
if(left[x] == 0) break;
x = left[x];
}
return x;
}
while(true){
if(par[x] == 0) return 0;
if(x == right[par[x]]){
x = par[x];
}else{
return par[x];
}
}
}
void sort_ta(){
sort(ta+1,ta+n/2);
}
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++){ // k log n
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();
for(i=1; i<n/2; i++) sa[i] = ta[i].second;
}
int wleft[150002],wright[150002];
int hleft[150002],hright[150002];
void set_tree(){
int i;
for(i=1; i<n/2; i++) hleft[i] = hright[i] = 999999999;
color[1] = true;
rb[1] = a[sa[1]].x;
root = 1;
before[1] = find_before(1);
next[1] = find_next(1);
for(i=2; i<n/2; i++){ // n log n
rb[i] = a[sa[i]].x;
rb_insert(i); // log n
before[i] = find_before(i); // log n
next[i] = find_next(i); // log n
if(before[i] != 0 && hright[before[i]] > a[sa[i]].y){
wright[before[i]] = i;
hright[before[i]] = a[sa[i]].y;
}
if(next[i] != 0 && hleft[next[i]] > a[sa[i]].y){
wleft[next[i]] = i;
hleft[next[i]] = a[sa[i]].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[sa[x]].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[sa[next[x]]].x;
if(before[x] != 0) dx -= a[sa[before[x]]+1].x;
dy = a[sa[x]].y - max(a[sa[before[x]]].y,a[sa[next[x]]].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();
tmp = aqua(1);
watertime = tmp.second;
print();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 3 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 8 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 9 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 10 |
Correct |
0 ms |
12368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 2 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12368 KB |
Output is correct |
| 4 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 5 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 6 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 7 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 8 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 9 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 10 |
Correct |
2 ms |
12368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12368 KB |
Output is correct |
| 3 |
Correct |
7 ms |
12368 KB |
Output is correct |
| 4 |
Correct |
3 ms |
12368 KB |
Output is correct |
| 5 |
Correct |
6 ms |
12368 KB |
Output is correct |
| 6 |
Correct |
12 ms |
12368 KB |
Output is correct |
| 7 |
Correct |
11 ms |
12368 KB |
Output is correct |
| 8 |
Correct |
5 ms |
12368 KB |
Output is correct |
| 9 |
Correct |
0 ms |
12368 KB |
Output is correct |
| 10 |
Correct |
2 ms |
12368 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
222 ms |
12368 KB |
Output is correct |
| 2 |
Correct |
201 ms |
12368 KB |
Output is correct |
| 3 |
Execution timed out |
1000 ms |
12364 KB |
Program timed out |
| 4 |
Halted |
0 ms |
0 KB |
- |
