제출 #581369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
581369		wdjpng	벽 (IOI14_wall)	C++17	100 / 100	1219 ms	162048 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

#define int long long
#define rep(i,n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
using namespace std;

struct s
{
    int minn = 0, maxx=1e15;
};

vector<s>T;
s def = s();
// s1 is new

int query(int i, int l, int r, int qi)
{
    if(l>qi||r<=qi) return -1;
    if(l+1==r) return i;
    return max(query(2*i,l,(l+r)/2,qi), query(2*i+1,(l+r)/2,r,qi));
}

void update(int i, int l, int r, int ul, int ur, bool add, int v)
{
    if(l>=ur||r<=ul) return;
    if(l>=ul&&r<=ur) {
        if(add) {
            T[i].minn=max(T[i].minn,v);
            T[i].maxx=max(T[i].maxx, v);
        }
        else { // cut down
            T[i].maxx=min(T[i].maxx, v); 
            T[i].minn=min(T[i].minn,v);
        }
        return;
    }
    
    if(T[i].minn!=def.minn||T[i].maxx!=def.maxx)
    {
        rep(j,2)
        {
            T[2*i+j].minn=max(T[2*i+j].minn,T[i].minn);
            T[2*i+j].maxx=max(T[2*i+j].maxx,T[i].minn);
            T[2*i+j].maxx=min(T[2*i+j].maxx,T[i].maxx); 
            T[2*i+j].minn=min(T[2*i+j].minn,T[i].maxx);
        }
        T[i]=def;
    }
    update(2*i,l,(l+r)/2,ul,ur,add,v);
    update(2*i+1,(l+r)/2,r,ul,ur,add,v);
}

void buildWall(signed n, signed k, signed op[], signed left[], signed right[], signed height[], signed finalHeight[]){
    T.assign(4*n+2,s());

    rep(ck,k)
    {
        update(1,0,n,left[ck],right[ck]+1,op[ck]==1,height[ck]);
    }

    rep(i,n) update(1,0,n,i,i+1,true,0);
    rep(i,n) finalHeight[i] = T[query(1,0,n,i)].minn;
}

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