oj.uz

Submission #243168

# Submission time Handle Problem Language Result Execution time Memory
243168 2020-06-30T13:22:18 Z Kubin Wall (IOI14_wall) C++17
100 / 100
 986 ms 59388 KB 
#include <bits/stdc++.h>

using namespace std;

struct clamp_op
{
    int a, b;
    int operator() (int x)
    {
        return min(max(x, a), b);
    }
} clamp_id = {INT_MIN, INT_MAX};

clamp_op operator>> (clamp_op F, clamp_op G)
{
    if(F.b < G.a)
        return {G.a, G.a};
    else if(G.b < F.a)
        return {G.b, G.b};
    else
        return {max(F.a, G.a), min(F.b, G.b)};
}
clamp_op& operator>>= (clamp_op& F, clamp_op G)
{
    return F = F >> G;
}
ostream& operator<< (ostream& out, clamp_op F)
{
    return out << "clamp_op{" << F.a << ", " << F.b << "}";
}

struct segment_tree
{
    size_t w;
    vector<clamp_op> values;

    segment_tree(size_t n) : w(1 << __lg(2*n - 1)), values(2*w, clamp_id) {}

    void push(size_t i)
    {
        if(i < w)
        {
            values[2*i+0] >>= values[i];
            values[2*i+1] >>= values[i];
            values[i] = clamp_id;
        }
    }

    void mut(size_t i, size_t nodeL, size_t nodeR, size_t L, size_t R, clamp_op F)
    {
        push(i);
        if(nodeR < L or R < nodeL)
            return;
        else if(L <= nodeL and nodeR <= R)
            values[i] >>= F;
        else
            mut(2*i+0, nodeL, (nodeL+nodeR)/2, L, R, F),
            mut(2*i+1, (nodeL+nodeR)/2+1, nodeR, L, R, F);
    }

    void mut(size_t L, size_t R, clamp_op F)
    {
        return mut(1, 0, w-1, L, R, F);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int out[])
{
    segment_tree tree(n);
    for(int i = 0; i < k; i++)
    {
        auto f = op[i] == 1 ? clamp_op{height[i], INT_MAX} : clamp_op{INT_MIN, height[i]};
        tree.mut(left[i], right[i], f);
    }
    for(int i = 1; i < (int)tree.w; i++)
        tree.push(i);
    for(int i = 0; i < n; i++)
        out[i] = tree.values[tree.w + i](0);
}

#ifdef XHOVA
int main()
{
    int out[10];
    int op[] = {1, 2, 2, 1, 1, 2}, left[] = {1, 4, 3, 0, 2, 6}, right[] = {8, 9, 6, 5, 2, 7}, height[] = {4, 1, 5, 3, 5, 0};
    buildWall(10, 6, op, left, right, height, out);
    for(auto x : out)
        cout << x << " ";
    cout << endl;
}
#endif

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 12 ms 768 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 11 ms 768 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 178 ms 14116 KB Output is correct
3 Correct 256 ms 8056 KB Output is correct
4 Correct 711 ms 20276 KB Output is correct
5 Correct 430 ms 20856 KB Output is correct
6 Correct 416 ms 19192 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 6 ms 512 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 768 KB Output is correct
5 Correct 11 ms 768 KB Output is correct
6 Correct 11 ms 768 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 176 ms 13944 KB Output is correct
9 Correct 255 ms 8056 KB Output is correct
10 Correct 708 ms 20344 KB Output is correct
11 Correct 423 ms 20728 KB Output is correct
12 Correct 420 ms 19192 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 176 ms 13920 KB Output is correct
15 Correct 53 ms 1920 KB Output is correct
16 Correct 900 ms 20344 KB Output is correct
17 Correct 432 ms 19704 KB Output is correct
18 Correct 429 ms 19704 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 7 ms 384 KB Output is correct
3 Correct 6 ms 384 KB Output is correct
4 Correct 13 ms 768 KB Output is correct
5 Correct 14 ms 768 KB Output is correct
6 Correct 11 ms 768 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 174 ms 14072 KB Output is correct
9 Correct 251 ms 7932 KB Output is correct
10 Correct 702 ms 20380 KB Output is correct
11 Correct 425 ms 20856 KB Output is correct
12 Correct 429 ms 19320 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 177 ms 14072 KB Output is correct
15 Correct 52 ms 1920 KB Output is correct
16 Correct 904 ms 20256 KB Output is correct
17 Correct 429 ms 19704 KB Output is correct
18 Correct 427 ms 19580 KB Output is correct
19 Correct 986 ms 59376 KB Output is correct
20 Correct 960 ms 59196 KB Output is correct
21 Correct 961 ms 59284 KB Output is correct
22 Correct 980 ms 59256 KB Output is correct
23 Correct 956 ms 59256 KB Output is correct
24 Correct 963 ms 59388 KB Output is correct
25 Correct 974 ms 59224 KB Output is correct
26 Correct 978 ms 59312 KB Output is correct
27 Correct 962 ms 59256 KB Output is correct
28 Correct 974 ms 59256 KB Output is correct
29 Correct 958 ms 59336 KB Output is correct
30 Correct 973 ms 59224 KB Output is correct