제출 #238232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238232		nicolaalexandra	벽 (IOI14_wall)	C++14	100 / 100	835 ms	77536 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
#define DIM 2000010
#define INF 2000000000
using namespace std;
struct segment_tree{
    int mini,maxi; /// astea sunt lazy urile
} aint[DIM*4];
int sol[DIM];

void update_lazy (int nod, int st, int dr){
    if (st == dr)
        return;
    int fiu_st = nod<<1, fiu_dr = (nod<<1)|1;
    aint[fiu_st].maxi = min (aint[fiu_st].maxi,aint[nod].mini);
    aint[fiu_st].mini = min (aint[fiu_st].mini,aint[nod].mini);

    aint[fiu_st].mini = max (aint[fiu_st].mini,aint[nod].maxi);
    aint[fiu_st].maxi = max (aint[fiu_st].maxi,aint[nod].maxi);

    ///
    aint[fiu_dr].maxi = min (aint[fiu_dr].maxi,aint[nod].mini);
    aint[fiu_dr].mini = min (aint[fiu_dr].mini,aint[nod].mini);

    aint[fiu_dr].mini = max (aint[fiu_dr].mini,aint[nod].maxi);
    aint[fiu_dr].maxi = max (aint[fiu_dr].maxi,aint[nod].maxi);

    aint[nod].mini = INF, aint[nod].maxi = 0;
}

void build (int nod, int st, int dr){
    aint[nod] = {INF,0};
    if (st == dr)
        return;

    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
}

void update_maxi (int nod, int st, int dr, int x, int y, int val){
    if (x <= st && dr <= y){
        aint[nod].maxi = max (aint[nod].maxi,val);
        aint[nod].mini = max (aint[nod].mini,val);
        return;
    }
    update_lazy(nod,st,dr);
    int mid = (st+dr)>>1;
    if (x <= mid)
        update_maxi (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update_maxi ((nod<<1)|1,mid+1,dr,x,y,val);

}

void update_mini (int nod, int st, int dr, int x, int y, int val){
    update_lazy(nod,st,dr);
    if (x <= st && dr <= y){
        aint[nod].mini = min (aint[nod].mini,val);
        aint[nod].maxi = min (aint[nod].maxi,val);
        return;
    }

    int mid = (st+dr)>>1;
    if (x <= mid)
        update_mini (nod<<1,st,mid,x,y,val);
    if (y > mid)
        update_mini ((nod<<1)|1,mid+1,dr,x,y,val);
}
void get_elem (int nod, int st, int dr){

    update_lazy (nod,st,dr);

    if (st == dr){
        sol[st] = aint[nod].maxi;
        return;
    }

    int mid = (st+dr)>>1;
    get_elem (nod<<1,st,mid);
    get_elem ((nod<<1)|1,mid+1,dr);
}
void buildWall (int n, int k, int op[], int Left[], int Right[], int v[], int finalHeight[]){

    build (1,0,n-1);
    for (int i=0;i<k;i++){
        if (op[i] == 1)
            update_maxi (1,0,n-1,Left[i],Right[i],v[i]);
        else update_mini (1,0,n-1,Left[i],Right[i],v[i]);
    }

    get_elem(1,0,n-1);

    for (int i=0;i<n;i++)
        finalHeight[i] = sol[i];

}

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