제출 #794765

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
794765		idiotcomputer	Wall (IOI14_wall)	C++11	0 / 100	119 ms	13912 KiB

wall

#include "wall.h"

const int MAX_N = 20000;
const int NINF = -1 * (1 << 30);
const int INF = (1<<30);

struct node {
    int tmin = -1;
    int tmax = -1;
    int opmin = INF;
    int opmax = NINF;
};

node segt[4*MAX_N+1];
void upd(int l, int r, int idx, int tl, int tr, int w, int h, int t){
    if (l > tr || r < tl){
        return;
    }
    if (l >= tl && r <= tr){
        //mini
        if (w == 1){
            if (h <= segt[idx].opmin || segt[idx].tmin == -1){
                segt[idx].opmin = h;
                segt[idx].tmin = t;
            }            
            if (h <= segt[idx].opmax || segt[idx].tmax == -1){
                segt[idx].opmax = h;
                segt[idx].tmax = t;
            }
        } else {
            if (h >= segt[idx].opmax || segt[idx].tmin == -1){
                segt[idx].opmax = h;
                segt[idx].tmax = t;
            }
            if (h >= segt[idx].opmin || segt[idx].tmax == -1){
                segt[idx].opmin = h;
                segt[idx].tmin = t;
            }
        }
        return;
    }
    int m = (l+r)/2;
    upd(l,m,2*idx+1,tl,tr,w,h,t);
    upd(m+1,r,2*idx+2,tl,tr,w,h,t);
    return;
}

void solve(int l, int r, int idx, int finalHeight[], node a){
    if (segt[idx].opmin <= a.opmax && segt[idx].tmin > a.tmax){
        a.opmax = segt[idx].opmin;
        a.tmax = segt[idx].tmin;
    } 
    if (segt[idx].opmin <= a.opmin && segt[idx].tmin > a.tmin){
        a.tmin = segt[idx].tmin;
        a.opmin = segt[idx].opmin;
    }
    if (segt[idx].opmax >= a.opmax && segt[idx].tmax > a.tmax){
        a.opmax = segt[idx].opmax;
        a.tmax = segt[idx].tmax;
    }
    if (segt[idx].opmax >= a.opmin && segt[idx].tmax > a.tmin){
        a.opmin = segt[idx].opmax;
        a.tmin = segt[idx].tmax;
    }
    if (l == r){
     /*   if (a.opmin != a.opmax){
            cout << "UHOHSPAGHETIIO "  << l << ' ' << r << " " << idx << " " << a.opmin << " " << a.opmax << '\n';
        }*/
        if (a.opmin == INF && a.opmax == NINF){
            finalHeight[l] = 0;
        } else if (a.opmin == INF){
            finalHeight[l] = a.opmax;
        } else if (a.opmax == INF){
            finalHeight[l] = a.opmin;
        } else {
            finalHeight[l] = a.opmin;
        }
        return;
    }
    int m = (l+r)/2;
    solve(l,m,2*idx+1,finalHeight,a);
    solve(m+1,r,2*idx+2,finalHeight,a);
    return;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    int l,r,w,h,idx;
    for (int i =0; i < k; i++){
        w = op[i]-1;
        h = height[i];
        idx = i;
        l = left[i];
        r = right[i];
        upd(0,n-1,0,l,r,w,h,idx);
    }
    
    node a;
    solve(0,n-1,0,finalHeight,a);
    return;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39