제출 #290611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290611		georgerapeanu	벽 (IOI14_wall)	C++11	100 / 100	966 ms	69624 KiB

wall

#include "wall.h"
#pragma once
#include <algorithm>
#include <cstdio>

using namespace std;

const int NMAX = 2e6;

pair<int,int> aint[4 * NMAX + 5];

void prop(pair<int,int> &a,pair<int,int> &b){
    if(a.second < b.first){
        b = {a.second,a.second};
    }
    else if(b.second < a.first){
        b = {a.first,a.first};
    }
    else{
        b = {max(a.first,b.first),min(a.second,b.second)};
    }
}

void propag(int nod,int st,int dr){
    if(st == dr){
        return ;
    }

    prop(aint[nod],aint[nod * 2]);
    prop(aint[nod],aint[nod * 2 + 1]);
    aint[nod] = {0,1e5};
}

void build(int nod,int st,int dr){
    aint[nod] = {0,1e5};

    if(st == dr){
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);
}

void update(int nod,int st,int dr,int op,int l,int r,int h){
    propag(nod,st,dr);
    if(dr < l || st > r){
        return ;
    }

    if(l <= st && dr <= r){
        pair<int,int> tmp = {0,1e5};
        if(op == 1){
            tmp.first = h;
        }
        else{
            tmp.second = h;
        }
        prop(tmp,aint[nod]);
        return ;
    }

    int mid = (st + dr) / 2;

    update(nod * 2,st,mid,op,l,r,h);
    update(nod * 2 + 1,mid + 1,dr,op,l,r,h);
}

void dfs(int nod,int st,int dr,int ans[]){
    propag(nod,st,dr);
    if(st == dr){
        ans[st - 1] = aint[nod].first;
        return ;
    }

    int mid = (st + dr) / 2;

    dfs(nod * 2,st,mid,ans);
    dfs(nod * 2 + 1,mid + 1,dr,ans);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    
    build(1,1,n);
    for(int i = 0;i < k;i++){
        update(1,1,n,op[i],left[i] + 1,right[i] + 1,height[i]);
    }

    dfs(1,1,n,finalHeight);
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp:2:9: warning: #pragma once in main file
    2 | #pragma once
      |         ^~~~

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