oj.uz

Submission #638415

# Submission time Handle Problem Language Result Execution time Memory
638415 2022-09-05T21:30:51 Z finn__ Wall (IOI14_wall) C++17
100 / 100
 1180 ms 92296 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 980 KB Output is correct
5 Correct 8 ms 1032 KB Output is correct
6 Correct 7 ms 956 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 147 ms 8220 KB Output is correct
3 Correct 212 ms 4644 KB Output is correct
4 Correct 603 ms 22132 KB Output is correct
5 Correct 370 ms 22780 KB Output is correct
6 Correct 347 ms 21212 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 8 ms 948 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 8 ms 1032 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 188 ms 13856 KB Output is correct
9 Correct 209 ms 8520 KB Output is correct
10 Correct 575 ms 22232 KB Output is correct
11 Correct 365 ms 22780 KB Output is correct
12 Correct 390 ms 21172 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 141 ms 13936 KB Output is correct
15 Correct 34 ms 2384 KB Output is correct
16 Correct 637 ms 22228 KB Output is correct
17 Correct 343 ms 21540 KB Output is correct
18 Correct 373 ms 21656 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 10 ms 980 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 6 ms 952 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 140 ms 13936 KB Output is correct
9 Correct 242 ms 8416 KB Output is correct
10 Correct 552 ms 22320 KB Output is correct
11 Correct 368 ms 22776 KB Output is correct
12 Correct 357 ms 21212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 142 ms 13932 KB Output is correct
15 Correct 37 ms 2356 KB Output is correct
16 Correct 580 ms 22232 KB Output is correct
17 Correct 363 ms 21660 KB Output is correct
18 Correct 354 ms 21580 KB Output is correct
19 Correct 1134 ms 91936 KB Output is correct
20 Correct 1151 ms 92112 KB Output is correct
21 Correct 1102 ms 92072 KB Output is correct
22 Correct 1106 ms 92032 KB Output is correct
23 Correct 1180 ms 92052 KB Output is correct
24 Correct 1116 ms 92048 KB Output is correct
25 Correct 1107 ms 91952 KB Output is correct
26 Correct 1124 ms 91996 KB Output is correct
27 Correct 1136 ms 92296 KB Output is correct
28 Correct 1118 ms 92144 KB Output is correct
29 Correct 1110 ms 92064 KB Output is correct
30 Correct 1104 ms 92036 KB Output is correct