제출 #242026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
242026		Coroian_David	Wall (IOI14_wall)	C++11	100 / 100	906 ms	77580 KiB

wall

#include <bits/stdc++.h>

//#include "wall.h"

#define MAX_N 2000000

using namespace std;

const int MAX = 100000;
const int MIN = 0;

int rez[MAX_N + 1];
struct aint
{
    int st, dr;
};

aint arb[(MAX_N << 2) + 1];

void upd(int poz, int st, int dr, int a, int b, int x, int y)
{
    //cout << "FACEM UPD " << poz << " " << st << " " << dr << " " << " INterv " << a << " " << b << " BVAL " << x << " " << y << "\n";

    if(st == a && dr == b)
    {
        if(x > arb[poz].dr)
        {
            arb[poz] = {x, x};
        }

        else
            if(y < arb[poz].st)
                arb[poz] = {y, y};

        else
        {
            arb[poz].st = max(arb[poz].st, x);
            arb[poz].dr = min(arb[poz].dr, y);
        }

        return;
    }

    int mid = (st + dr) >> 1;

    upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
    upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);

    arb[poz] = {MIN, MAX};

    if(b <= mid)
        upd(poz << 1, st, mid, a, b, x, y);

    if(a > mid)
        upd((poz << 1) + 1, mid + 1, dr, a, b, x, y);

    if(a <= mid && b > mid)
    {
        upd(poz << 1, st, mid, a, mid, x, y);
        upd((poz << 1) + 1, mid + 1, dr, mid + 1, b, x, y);
    }
}

void build(int poz, int st, int dr)
{
    arb[poz] = {MIN, MAX};

    if(st == dr)
        return;

    int mid = (st + dr) >> 1;

    build(poz << 1, st, mid);
    build((poz << 1) + 1, mid + 1, dr);
}

void dfs(int poz, int st, int dr)
{
    if(st == dr)
    {
        rez[st] = arb[poz].st;

        return;
    }

    int mid = (st + dr) >> 1;

    upd(poz << 1, st, mid, st, mid, arb[poz].st, arb[poz].dr);
    upd((poz << 1) + 1, mid + 1, dr, mid + 1, dr, arb[poz].st, arb[poz].dr);

    arb[poz] = {MIN, MAX};

    dfs(poz << 1, st, mid);
    dfs((poz << 1) + 1, mid + 1, dr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
    build(1, 1, n);

    for(int i = 0; i < k; i ++)
    {
        int st = left[i] + 1;
        int dr = right[i] + 1;
        int nr = height[i];

        if(op[i] == 2)
            upd(1, 1, n, st, dr, MIN, nr);

        else
            upd(1, 1, n, st, dr, nr, MAX);
    }

    dfs(1, 1, n);

    for(int i = 0; i < n; i ++)
        finalHeight[i] = rez[i + 1];
}

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