제출 #92563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92563		maruii	벽 (IOI14_wall)	C++17	100 / 100	1218 ms	64460 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1<<21;
int *fin;
struct ST{
    int mn[2*SIZE], mx[2*SIZE];
    void update(int nn, int ns, int ne, int s, int e, int x, int q){
        if(ns>e || ne<s) return;
        if(s<=ns && ne<=e){
            if(q==1){
                mn[nn] = max(mn[nn], x);
                mx[nn] = max(mx[nn], x);
            } else if(q==2){
                mn[nn] = min(mn[nn], x);
                mx[nn] = min(mx[nn], x);
            }
            if(ns==ne) fin[ns] = mx[nn];
            return;
        }
        int m =(ns+ne)/2;
        int l = nn*2, r = l+1;
        mn[l] = min(mn[l], mn[nn]); mn[r] = min(mn[r], mn[nn]);
        mx[l] = min(mx[l], mn[nn]); mx[r] = min(mx[r], mn[nn]);
        mn[l] = max(mn[l], mx[nn]); mn[r] = max(mn[r], mx[nn]);
        mx[l] = max(mx[l], mx[nn]); mx[r] = max(mx[r], mx[nn]);
        mx[nn] = 0; mn[nn] = 1e9;
        update(l, ns, m, s, e, x, q);
        update(r, m+1, ne, s, e, x, q);
    }
}seg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    fin = finalHeight;
    for(int i=0; i<k; ++i){
        seg.update(1, 0, n-1, left[i], right[i], height[i], op[i]);
    }
    for(int i=0; i<n; ++i)
        seg.update(1, 0, n-1, i, i, 0, 0);
    return;
}

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