제출 #638404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
638404		finn__	Wall (IOI14_wall)	C++17	0 / 100	136 ms	13836 KiB

wall

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

struct segtree
{
    vector<long> lower, upper;
    size_t l;

    segtree(size_t n)
    {
        l = 1 << (32 - __builtin_clz(n));
        lower = vector<long>(2 * l, 0);
        upper = vector<long>(2 * l, 0);
    }

    void propagate(size_t k, size_t x, size_t y)
    {
        if (k < l)
        {
            upper[2 * k] = max(min(upper[k], upper[2 * k]), lower[k]);
            upper[2 * k + 1] = max(min(upper[k], upper[2 * k + 1]), lower[k]);
            lower[2 * k + 1] = min(max(lower[k], lower[2 * k]), upper[k]);
            lower[2 * k + 1] = min(max(lower[k], lower[2 * k + 1]), upper[k]);
        }
    }

    void update(size_t i, size_t j, long v, bool is_lower, size_t k, size_t x, size_t y)
    {
        if (x > y || y < i || x > j)
            return;
        if (i <= x && y <= j)
        {
            if (is_lower)
            {
                lower[k] = max(lower[k], v);
                upper[k] = max(upper[k], lower[k]);
            }
            else
            {
                upper[k] = min(upper[k], v);
                lower[k] = min(lower[k], upper[k]);
            }
        }
        else
        {
            propagate(k, x, y);
            update(i, j, v, is_lower, 2 * k, x, (x + y) / 2);
            update(i, j, v, is_lower, 2 * k + 1, (x + y) / 2 + 1, y);
        }
    }

    long point_val(size_t i, size_t k, size_t x, size_t y)
    {
        if (x == y)
            return lower[k];

        propagate(k, x, y);

        if (i <= (x + y) / 2)
            return point_val(i, 2 * k, x, (x + y) / 2);
        else
            return point_val(i, 2 * k + 1, (x + y) / 2 + 1, y);
    }
};

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

    for (size_t i = 0; i < k; i++)
        tree.update(left[i], right[i], height[i], op[i] == 1, 1, 0, tree.l - 1);

    for (size_t i = 0; i < n; i++)
        finalHeight[i] = tree.point_val(i, 1, 0, tree.l - 1);
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:70:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     for (size_t i = 0; i < k; i++)
      |                        ~~^~~
wall.cpp:73:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |     for (size_t i = 0; i < n; i++)
      |                        ~~^~~

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