제출 #938838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
938838		codefox	벽 (IOI14_wall)	C++14	100 / 100	594 ms	70228 KiB

wall

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

using namespace std;

int N = 1<<21;
vector<int> bmn(2*N, 0);
vector<int> bmx(2*N, 0);
int ox, on;

void update(int curr, int l, int r, int ll, int rr, int mx, int mn)
{
    if (mx < bmx[curr])
    {
        bmx[curr] = mx;
        if (bmx[curr]<bmn[curr] && mn <= bmn[curr]) bmn[curr] = bmx[curr];
    }
    if (mn > bmn[curr])
    {
        bmn[curr] = mn;
        if(bmx[curr]<bmn[curr]) bmx[curr] = bmn[curr];
    }

    if (l >= rr || r <= ll) return;
    if (l >= ll && r <= rr) 
    {
        if (ox != -1) 
        {
            if (bmn[curr]>ox) bmn[curr] = ox;
            bmx[curr] = min(ox, bmx[curr]);
        }
        else
        {
            if (bmx[curr]<on) bmx[curr] = on;  
            bmn[curr] = max(bmn[curr], on); 
        }
        return;
    }
    
    if (mx > bmx[curr])
    {
        mx = bmx[curr];
        if (mx < mn && mn >= bmn[curr]) mn = mx;
    }
    if (mn < bmn[curr])
    {
        mn = bmn[curr];
        if (mx < mn) mx = mn;
    }

    int m = (r+l)/2;
    update(curr*2, l, m, ll, rr, mx, mn);
    update(curr*2+1, m, r, ll, rr, mx, mn);
    bmn[curr] = min(bmn[curr*2], bmn[curr*2+1]);
    bmx[curr] = max(bmx[curr*2], bmx[curr*2+1]);
}

void dfs(int curr, int mx, int mn)
{
    if (mx < bmx[curr])
    {
        bmx[curr] = mx;
        if (bmx[curr]<bmn[curr] && mn <= bmn[curr]) bmn[curr] = bmx[curr];
    }
    if (mn > bmn[curr])
    {
        bmn[curr] = mn;
        if(bmx[curr]<bmn[curr]) bmx[curr] = bmn[curr];
    }

    if (mx > bmx[curr])
    {
        mx = bmx[curr];
        if (mx < mn && mn >= bmn[curr]) mn = mx;
    }
    if (mn < bmn[curr])
    {
        mn = bmn[curr];
        if (mx < mn) mx = mn;
    }

    if (curr >= N) return;

    dfs(curr*2, mx, mn);
    dfs(curr*2+1, mx, mn);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    for (int i = 0; i < k; i++)
    {
        on = -1;
        ox = -1;
        if (op[i]==1) on = height[i];
        else ox = height[i];
        update(1, 0, N, left[i], right[i]+1, 1e9, 0);
    }
    dfs(1, 1e9, 0);
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = bmx[i+N];
    }
    return;
}


/*
int main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;

    int op[k];
    int left[k];
    int right[k];
    int height[k];
    int finalHeight[n];

    for (int i =0; i < k; i++)
    {
        cin >> op[i];
        cin >> left[i];
        cin >> right[i];
        cin >> height[i];
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int ele:finalHeight) cout << ele << " ";

    return 0;
}
*/

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