제출 #290293

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
290293		AaronNaidu	벽 (IOI14_wall)	C++14	0 / 100	225 ms	10236 KiB

wall

#include <bits/stdc++.h>
using namespace std;

const int pow2 = 131072;

int segTree[2*pow2];
//pair<int, int> lazyMin[2*pow2];
//pair<int, int> lazyMax[2*pow2];
int lazyUpdate[2*pow2];
int lazyMin[2*pow2];

set<pair<pair<int, int>, int> > s;

void setMax(int node, int nodeStart, int nodeEnd, int rangeStart, int rangeEnd, int amount) {
    if (nodeStart > rangeEnd or nodeEnd < rangeStart)
    {
        return;
    }
    /*if (node >= pow2)
    {
        if (lazyUpdate[node] != -1)
        {             
            segTree[node] = max(lazyUpdate[node], segTree[node]);
            lazyUpdate[node] = -1;
        }
        segTree[node] = max(amount, segTree[node]);
        return;
    }
    if (lazyUpdate[node] != -1)
    {
        //segTree[node] = max(lazyUpdate[node], segTree[node]);
        lazyUpdate[2*node] = max(lazyUpdate[2*node], lazyUpdate[node]);
        lazyUpdate[2*node+1] = max(lazyUpdate[2*node+1], lazyUpdate[node]);
    }*/
    if (nodeStart >= rangeStart and nodeEnd <= rangeEnd)
    {
        lazyUpdate[node] = max(lazyUpdate[node], amount);
        return;
    }
    int med = (nodeStart + nodeEnd)/2;
    setMax(2*node, nodeStart, med, rangeStart, rangeEnd, amount);
    setMax(2*node+1, med+1, nodeEnd, rangeStart, rangeEnd, amount);
}

void setMin(int node, int nodeStart, int nodeEnd, int rangeStart, int rangeEnd, int amount) {
    if (nodeStart > rangeEnd or nodeEnd < rangeStart)
    {
        return;
    }
    /*if (node >= pow2)
    {
        if (lazyUpdate[node] != -1)
        {             
            segTree[node] = max(lazyUpdate[node], segTree[node]);
            lazyUpdate[node] = -1;
        }
        segTree[node] = max(amount, segTree[node]);
        return;
    }
    if (lazyUpdate[node] != -1)
    {
        //segTree[node] = max(lazyUpdate[node], segTree[node]);
        lazyUpdate[2*node] = max(lazyUpdate[2*node], lazyUpdate[node]);
        lazyUpdate[2*node+1] = max(lazyUpdate[2*node+1], lazyUpdate[node]);
    }*/
    if (nodeStart >= rangeStart and nodeEnd <= rangeEnd)
    {
        lazyMin[node] = min(lazyMin[node], amount);
        return;
    }
    int med = (nodeStart + nodeEnd)/2;
    setMin(2*node, nodeStart, med, rangeStart, rangeEnd, amount);
    setMin(2*node+1, med+1, nodeEnd, rangeStart, rangeEnd, amount);
}

void buildWall(int n, int k, int op[],int left[],int right[],int heights[],int finalHeight[]) {
    for (int i = 0; i < n; i++)
    {
        finalHeight[i] = 0;
    }
    int turningPoint = n;
    for (int i = 0; i < n; i++)
    {
        if (op[i] == 2)
        {
            turningPoint = i;
            break;
        }
    }
    for (int i = 0; i < 2*pow2; i++)
    {
        lazyUpdate[i] = 0;
        lazyMin[i] = 1000000007;
    }

    for (int i = 0; i < turningPoint; i++)
    {
        setMax(1, 0, pow2-1, left[i], right[i], heights[i]);
    }
    for (int i = turningPoint; i < n; i++)
    {
        setMin(1, 0, pow2-1, left[i], right[i], heights[i]);
    }
    for (int i = 1; i < 2*pow2; i++)
    {
        lazyUpdate[i] = max(lazyUpdate[i], lazyUpdate[i/2]);
        lazyMin[i] = min(lazyMin[i], lazyMin[i/2]);
    }
    for (int i = 0; i < n; i++)
    {
        if (lazyMin[i+pow2] == 1000000007)
        {
            finalHeight[i] = lazyUpdate[i+pow2];
        }
        else
        {
            finalHeight[i] = min(lazyMin[i+pow2], lazyUpdate[i+pow2]);
        }
    }
}

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