Submission #638415

#	Time	Username	Problem	Language	Result	Execution time	Memory
638415		finn__	Wall (IOI14_wall)	C++17	100 / 100	1180 ms	92296 KiB

wall

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

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

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

    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] = 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, int64_t 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);
            lower[k] = min(lower[k], min(lower[2 * k], lower[2 * k + 1]));
            upper[k] = max(upper[k], max(upper[2 * k], upper[2 * k + 1]));
        }
    }

    int64_t 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 j = 0; j < tree.lower.size(); j++)
        //     cout << "(" << tree.lower[j] << ", " << tree.upper[j] << ")\n";
        // cout << "\n\n";
    }

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

Compilation message (stderr)

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

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