oj.uz

Submission #773747

# Submission time Handle Problem Language Result Execution time Memory
773747 2023-07-05T08:06:52 Z boris_mihov Wall (IOI14_wall) C++17
100 / 100
 613 ms 130724 KB 
#include "wall.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

typedef long long llong;
const int MAXN = 2000000 + 10;
const int INF  = 1e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        int min;
        int max;
        int lazy;

        Node()
        {
            min = max = 0;
            lazy = -1;
        }
    };

    Node tree[4*MAXN];
    Node combine(Node left, Node right)
    {
        Node res;
        res.min = std::min(left.min, right.min);
        res.max = std::max(left.max, right.max);
        return res;
    }

    void push(int node, int l, int r)
    {
        if (tree[node].lazy == -1)
        {
            return;
        }

        tree[node].min = tree[node].lazy;
        tree[node].max = tree[node].lazy;
    
        if (l < r)
        {
            tree[2*node].lazy = tree[node].lazy;
            tree[2*node + 1].lazy = tree[node].lazy;
        }

        tree[node].lazy = -1;
    }

    void updateMAX(int l, int r, int node, int queryL, int queryR, int val)
    {
        push(node, l, r);
        if (r < queryL || queryR < l || tree[node].min >= val)
        {
            return;
        }

        if (queryL <= l && r <= queryR && tree[node].max <= val)
        {
            tree[node].lazy = val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        updateMAX(l, mid, 2*node, queryL, queryR, val);
        updateMAX(mid + 1, r, 2*node + 1, queryL, queryR, val);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void updateMIN(int l, int r, int node, int queryL, int queryR, int val)
    {
        push(node, l, r);
        if (r < queryL || queryR < l || tree[node].max <= val)
        {
            return;
        }

        if (queryL <= l && r <= queryR && tree[node].min >= val)
        {
            tree[node].lazy = val;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        updateMIN(l, mid, 2*node, queryL, queryR, val);
        updateMIN(mid + 1, r, 2*node + 1, queryL, queryR, val);
        tree[node] = combine(tree[2*node], tree[2*node + 1]);
    }

    void assignANS(int l, int r, int node, int to[])
    {
        push(node, l, r);
        if (l == r)
        {
            to[l - 1] = tree[node].min;
            return;
        }

        int mid = (l + r) / 2;
        assignANS(l, mid, 2*node, to);
        assignANS(mid + 1, r, 2*node + 1, to);
    }

    void updateMIN(int l, int r, int val)
    {
        updateMIN(1, n, 1, l, r, val);
    }

    void updateMAX(int l, int r, int val)
    {
        updateMAX(1, n, 1, l, r, val);
    }

    void assignANS(int to[])
    {
        assignANS(1, n, 1, to);
    }
};

SegmentTree tree;
void buildWall(int N, int Q, int op[], int left[], int right[], int height[], int finalHeight[])
{
    n = N;
    q = Q;

    for (int i = 0 ; i < q ; ++i)
    {
        if (op[i] == 1)
        {
            tree.updateMAX(left[i] + 1, right[i] + 1, height[i]);
        } else
        {
            tree.updateMIN(left[i] + 1, right[i] + 1, height[i]);
        }
    }

    tree.assignANS(finalHeight);
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94224 KB Output is correct
2 Correct 41 ms 94348 KB Output is correct
3 Correct 43 ms 94164 KB Output is correct
4 Correct 42 ms 94472 KB Output is correct
5 Correct 44 ms 94412 KB Output is correct
6 Correct 42 ms 94436 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 94136 KB Output is correct
2 Correct 170 ms 107788 KB Output is correct
3 Correct 109 ms 101328 KB Output is correct
4 Correct 193 ms 112240 KB Output is correct
5 Correct 206 ms 113244 KB Output is correct
6 Correct 233 ms 111700 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94192 KB Output is correct
2 Correct 40 ms 94248 KB Output is correct
3 Correct 41 ms 94228 KB Output is correct
4 Correct 44 ms 94356 KB Output is correct
5 Correct 44 ms 94424 KB Output is correct
6 Correct 49 ms 94416 KB Output is correct
7 Correct 40 ms 94124 KB Output is correct
8 Correct 154 ms 107864 KB Output is correct
9 Correct 97 ms 101268 KB Output is correct
10 Correct 195 ms 112180 KB Output is correct
11 Correct 194 ms 113184 KB Output is correct
12 Correct 204 ms 111692 KB Output is correct
13 Correct 48 ms 94228 KB Output is correct
14 Correct 155 ms 107796 KB Output is correct
15 Correct 70 ms 95348 KB Output is correct
16 Correct 420 ms 112440 KB Output is correct
17 Correct 273 ms 111824 KB Output is correct
18 Correct 274 ms 111900 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94164 KB Output is correct
2 Correct 42 ms 94328 KB Output is correct
3 Correct 41 ms 94208 KB Output is correct
4 Correct 45 ms 94412 KB Output is correct
5 Correct 45 ms 94364 KB Output is correct
6 Correct 43 ms 94416 KB Output is correct
7 Correct 41 ms 94132 KB Output is correct
8 Correct 149 ms 107852 KB Output is correct
9 Correct 98 ms 101324 KB Output is correct
10 Correct 177 ms 112228 KB Output is correct
11 Correct 183 ms 113312 KB Output is correct
12 Correct 198 ms 111680 KB Output is correct
13 Correct 41 ms 94144 KB Output is correct
14 Correct 166 ms 107804 KB Output is correct
15 Correct 62 ms 95360 KB Output is correct
16 Correct 389 ms 112444 KB Output is correct
17 Correct 273 ms 111848 KB Output is correct
18 Correct 266 ms 111840 KB Output is correct
19 Correct 567 ms 130560 KB Output is correct
20 Correct 550 ms 128196 KB Output is correct
21 Correct 563 ms 130584 KB Output is correct
22 Correct 613 ms 128064 KB Output is correct
23 Correct 544 ms 128116 KB Output is correct
24 Correct 576 ms 128116 KB Output is correct
25 Correct 541 ms 127992 KB Output is correct
26 Correct 551 ms 130724 KB Output is correct
27 Correct 576 ms 130556 KB Output is correct
28 Correct 568 ms 128080 KB Output is correct
29 Correct 547 ms 128220 KB Output is correct
30 Correct 553 ms 128036 KB Output is correct