제출 #516252

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
516252		status_coding	벽 (IOI14_wall)	C++14	0 / 100	147 ms	9608 KiB

wall

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

using namespace std;

struct segS
{
    pair<int, int> val= {0, 0};
    bool lazy = false;
};

vector<segS> seg;

void calc(int p, pair<int, int> val)
{
    if(val.first > seg[p].val.second)
        seg[p].val = {val.first, val.first};

    else if(val.second < seg[p].val.first)
        seg[p].val = {val.second, val.second};

    else
    {
        seg[p].val.first = max(seg[p].val.first, val.first);
        seg[p].val.second = min(seg[p].val.second, val.second);
    }

    seg[p].lazy = true;
}

void push(int p)
{
    if(!seg[p].lazy)
        return;

    calc(2*p, seg[p].val);
    calc(2*p+1, seg[p].val);
    seg[p].lazy=false;
}

void upd(int stt, int drt, int st, int dr, int p, pair<int, int> val)
{
    if(stt == st && drt == dr)
    {
        calc(p, val);
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    if(drt <= mij)
        upd(stt, drt, st, mij, 2*p, val);
    else if(stt > mij)
        upd(stt, drt, mij+1, dr, 2*p+1, val);
    else
    {
        upd(stt, mij, st, mij, 2*p, val);
        upd(mij+1, drt, mij+1, dr, 2*p+1, val);
    }
}

void pushAll(int st, int dr, int p, int ans[])
{
    if(st == dr)
    {
        ans[st] = seg[p].val.first;
        return;
    }

    push(p);

    int mij=(st+dr)/2;

    pushAll(st, mij, 2*p, ans);
    pushAll(mij+1, dr, 2*p+1, ans);
}

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[])
{
    seg.resize(4*n + 4);

    for(int i=0; i<k; i++)
    {
        if(op[i] == 1)
            upd(l[i], r[i], 0, n-1, 1, {h[i], 1e9});
        else
            upd(l[i], r[i], 0, n-1, 1, {-1e9, h[i]});
    }

    pushAll(0, n-1, 1, ans);
}

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