제출 #996001

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
996001		Icelast	벽 (IOI14_wall)	C++17	100 / 100	1326 ms	92244 KiB

wall

#include "wall.h"
#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 1e9+9;
struct SegmentTree{
    struct Node{
        ll chmn, chmx;
    };
    ll n, N;
    vector<Node> T;
    SegmentTree(int n) : n(n){
        N = 1;
        while(N < n) N*=2;
        T.resize(N*2+1, {INF, -INF});
    };
    Node combine(Node a, Node b){
        if(b.chmn >= a.chmn){
            //nothing changed
        }else if(b.chmn >= a.chmx && b.chmn < a.chmn){
            a.chmn = b.chmn;
        }else if(b.chmn < a.chmx){
            a.chmn = b.chmn;
            a.chmx = b.chmn;
        }
        if(b.chmx >= a.chmn){
            a.chmn = b.chmx;
            a.chmx = b.chmx;
        }else if(b.chmx >= a.chmx && b.chmx < a.chmn){
            a.chmx = b.chmx;
        }else if(b.chmx < a.chmx){
            //nothing changed;
        }
        return a;
    }
    void down(int node){
        for(int child = node*2; child <= node*2+1; child++){
            if(child >= 2*N) return;
            T[child] = combine(T[child], T[node]);
        }
        T[node] = {INF, -INF};
    }
    void upd(int l, int r, int ch, ll x){
        auto upd = [&](auto upd, int node, int low, int high, int l, int r, int ch, ll x) -> void{
            down(node);
            if(low > r || l > high) return;
            if(low >= l && r >= high){
                Node X;
                if(ch == 1){
                    X = {INF, x};
                }else{
                    X = {x, -INF};
                }
                T[node] = combine(T[node], X);
                down(node);
                return;
            }
            int mid = (low+high)/2;
            upd(upd, node*2, low, mid, l, r, ch, x);
            upd(upd, node*2+1, mid+1, high, l, r, ch, x);
        };
        upd(upd, 1, 1, N, l, r, ch, x);
    }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    SegmentTree T(n+5);
    for(int i = 0; i < k; i++){
        T.upd(left[i]+1, right[i]+1, op[i], height[i]);
    }
    for(int i = 1; i <= n; i++){
        T.upd(i, i, 1, -INF);
    }
    for(int i = 1; i <= n; i++){
        ll val = 0;
        val = min(val, T.T[i+T.N-1].chmn);
        val = max(val, T.T[i+T.N-1].chmx);
        finalHeight[i-1] = val;
    }
    return;
}

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