Submission #16743

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
16743	2015-09-13T08:05:22 Z	suhgyuho_william	수족관 2 (KOI13_aqua2)	C++	69 / 100	1000 ms	11196 KB

aqua2

#include <stdio.h>
#include <algorithm>
using namespace std;

int n,k;

struct data{
    int x,y;
    bool hole;
}a[300002];
int sa[150002];

bool cmp(int cx,int cy){
    if(a[cx].y < a[cy].y) return true;
    if(a[cx].y == a[cy].y && a[cx].x < a[cy].x) return true;
    return false;
}

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;
}

void rb_insert(int x){
    int y;
    int grand;

    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 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++) sa[i] = i*2;
    sort(sa+1,sa+(n/2),cmp);
}

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++){
        rb[i] = a[sa[i]].x;
        rb_insert(i);
        before[i] = find_before(i);
        next[i] = find_next(i);
        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;

pair<int,double> aqua(int x){
    int i;
    int dx,dy;
    int big;
    int hole;
    long long water;
    double ltime,rtime,big2;

    //printf("%d ",sa[x]);
    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;
    big = max(a[sa[before[x]]].y,a[sa[next[x]]].y);
    dy = a[sa[x]].y - big;
    water = (long long)dx * (long long)dy;
    if(a[sa[x]].hole == true) hole = 1;
    else hole = 0;
    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(hole == 0){
        leftwater += water;
        return make_pair(0,0);
    }
    big2 = (double)water / (double)hole;
    big2 += max(ltime,rtime);
    return make_pair(hole,big2);
}

void print(){
    printf("%.2f\n",watertime);
    printf("%lld",leftwater);
}

int main(void){
    Input();
    set_tree();
    tmp = aqua(1);
    watertime = tmp.second;
    print();

    return 0;
}

Subtask #1
13.0 / 13.0

#	Verdict	Memory	Grader output
1	Correct	11196 KB	Output is correct
2	Correct	11196 KB	Output is correct
3	Correct	11196 KB	Output is correct
4	Correct	11196 KB	Output is correct
5	Correct	11196 KB	Output is correct
6	Correct	11196 KB	Output is correct
7	Correct	11196 KB	Output is correct
8	Correct	11196 KB	Output is correct
9	Correct	11196 KB	Output is correct
10	Correct	11196 KB	Output is correct

Subtask #2
21.0 / 21.0

#	Verdict	Memory	Grader output
1	Correct	11196 KB	Output is correct
2	Correct	11196 KB	Output is correct
3	Correct	11196 KB	Output is correct
4	Correct	11196 KB	Output is correct
5	Correct	11196 KB	Output is correct
6	Correct	11196 KB	Output is correct
7	Correct	11196 KB	Output is correct
8	Correct	11196 KB	Output is correct
9	Correct	11196 KB	Output is correct
10	Correct	11196 KB	Output is correct

Subtask #3
35.0 / 35.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	11196 KB	Output is correct
2	Correct	2 ms	11196 KB	Output is correct
3	Correct	7 ms	11196 KB	Output is correct
4	Correct	3 ms	11196 KB	Output is correct
5	Correct	6 ms	11196 KB	Output is correct
6	Correct	12 ms	11196 KB	Output is correct
7	Correct	10 ms	11196 KB	Output is correct
8	Correct	5 ms	11196 KB	Output is correct
9	Correct	0 ms	11196 KB	Output is correct
10	Correct	0 ms	11196 KB	Output is correct

Subtask #4
0.0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	233 ms	11196 KB	Output is correct
2	Correct	237 ms	11196 KB	Output is correct
3	Execution timed out	1000 ms	11192 KB	Program timed out
4	Halted	0 ms	0 KB	-

Submission #16743

Compilation message

Subtask #1 13.0 / 13.0

Subtask #2 21.0 / 21.0

Subtask #3 35.0 / 35.0

Subtask #4 0.0 / 31.0

Subtask #1
13.0 / 13.0

Subtask #2
21.0 / 21.0

Subtask #3
35.0 / 35.0

Subtask #4
0.0 / 31.0