Submission #16766

#	Time	Username	Problem	Language	Result	Execution time	Memory
16766		suhgyuho_william	수족관 2 (KOI13_aqua2)	C++98	0 / 100	150 ms	12212 KiB

aqua2

#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];
int 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];
        }
    }
    free(right_node);
    free(right_y);
    free(left_node);
    free(left_y);
    free(ttt);
}


int before[150002],next[150002];
int wleft[150002],wright[150002];
int hleft[150002],hright[150002];

void set_tree2(){
    int i,index;

    for(i=1; i<n/2; i++){
        hleft[i] = hright[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 && hright[before[i]] > a[ta[i].second].y){
            wright[before[i]] = i;
            hright[before[i]] = a[ta[i].second].y;
        }
        if(next[i] != 0 && hleft[next[i]] > a[ta[i].second].y){
            wleft[next[i]] = i;
            hleft[next[i]] = a[ta[i].second].y;
        }
    }
    free(before);
    free(next);
    free(hleft);
    free(hright);
}

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

• Subtask 1: 0 / 13
• Subtask 2: 0 / 21
• Subtask 3: 0 / 35
• Subtask 4: 0 / 31