oj.uz

Submission #749706

# Submission time Handle Problem Language Result Execution time Memory
749706 2023-05-28T11:52:18 Z adrilen Wall (IOI14_wall) C++17
24 / 100
 537 ms 36968 KB 
#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
constexpr int maxn = 2e6 + 5, bit = 32 - __builtin_clz(maxn), siz = 1 << bit;

struct Node {
    int val;
    bool empty, is_max, fini;

    void comp(const Node &other) {

        if (other.empty) return ;

        if (empty || other.fini) {
            val = other.val, empty = other.empty, is_max = other.is_max, fini = other.fini;

        }
        else if (is_max)
        {
            if (other.is_max)
            {
                val = max(val, other.val);
            } else {
                if (other.val < val)
                {
                    val = other.val;
                    is_max = false;
                    fini = true;
                }
            }
        } else {
            if (other.is_max)
            {
                if (other.val > val)
                {
                    val = other.val;
                    is_max = true;
                    fini = true;
                } 
            } else {
                val = min(val, other.val);
            }
        }
    }
} ;

Node defa = Node{0, true, false, false};

Node segtree[siz * 2] = { 0 };


void propogate(int pos)
{
    segtree[pos * 2].comp(segtree[pos]);
    segtree[pos * 2 + 1].comp(segtree[pos]);

    segtree[pos] = defa;
}

void update(int pos, int l, int r, int gl, int gr, Node p)
{
    if (gl > r || l > gr) return ;

    // Inside
    if (gl <= l && r <= gr)
    {
        segtree[pos].comp(p);
        return ;
    }

    propogate(pos);
    int mid = (l + r) >> 1;
    update(pos * 2, l, mid, gl, gr, p);
    update(pos * 2 + 1, mid + 1, r, gl, gr, p);
}

int output[maxn] = { 0 };

void fnd_answers(int pos, int l, int r, int gl, int gr)
{
    if (l > gr || gl > r) return ;
    // cout << pos << endl;

    if (segtree[pos].fini)
    {
        for (int i = l; i <= r; i++) output[i] = segtree[pos].val;
        return ;
    }

    propogate(pos);
    int mid = (l + r) >> 1;
    fnd_answers(pos * 2, l, mid, gl, gr);
    fnd_answers(pos * 2 + 1, mid + 1, r, gl, gr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
    for (int i = 1; i < siz; i++) segtree[i].empty = true;
    for (int i = siz; i < siz + n; i++) segtree[i].fini = true;

    for (int i = 0; i < k; i++)
    {
        // cout << i << "\n";
        update(1, 0, siz - 1, left[i], right[i], Node{height[i], false, (bool)(op[i] & 1), false});
        // for (int i = 1; i < 2 * siz; i++)
        // {
        //     if (__builtin_popcount(i) == 1) cout << "\n";
        //     cout << segtree[i].val << " " << segtree[i].is_max << " " << segtree[i].empty << " " << segtree[i].fini << "    ";
        // }
        // cout << "\n\n";
    }

    fnd_answers(1, 0, siz - 1, 0, n - 1);

    for (int i = 0; i < n; i++) finalHeight[i] = output[i];
    return ;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 10 ms 16856 KB Output is correct
3 Incorrect 9 ms 16724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 16724 KB Output is correct
2 Correct 226 ms 30376 KB Output is correct
3 Correct 193 ms 24112 KB Output is correct
4 Correct 537 ms 35992 KB Output is correct
5 Correct 267 ms 36968 KB Output is correct
6 Correct 259 ms 35364 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 12 ms 16832 KB Output is correct
3 Incorrect 10 ms 16704 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 16724 KB Output is correct
2 Correct 10 ms 16828 KB Output is correct
3 Incorrect 9 ms 16708 KB Output isn't correct
4 Halted 0 ms 0 KB -