oj.uz

Submission #752568

# Submission time Handle Problem Language Result Execution time Memory
752568 2023-06-03T08:35:23 Z adrilen Wall (IOI14_wall) C++17
0 / 100
 661 ms 52672 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, max_val = 1e9;

const array<int, 2> defa = {0, max_val};

array<int, 2> segtree[siz * 2] = { 0 };

void comp(array<int, 2> &lower, const array<int,2>&over)
{
    if (over[1] < lower[0])
    {
        lower[0] = lower[1] = over[1];
    } else if (over[0] > lower[1])
    {
        lower[0] = lower[1] = over[0];
    } else if (lower[0] <= over[0] && over[1] <= lower[1]) {
        lower = over;
    } else {
        lower[0] = max(lower[0], over[0]);
        lower[1] = min(lower[1], over[1]);
    }
}

void propogate(int p)
{
    comp(segtree[p * 2], segtree[p]);
    comp(segtree[p * 2 + 1], segtree[p]);
    segtree[p] = defa;
}

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

    // Inside
    if (gl <= l && r <= gr)
    {
        comp(segtree[pos], 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 ;

    if (segtree[pos][0] == segtree[pos][1])
    {
        for (int i = l; i <= r; i++) output[i] = segtree[pos][0];
        // cout << "finished: " <<l  << " " << r << "\n";
        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 = 0; i < siz; i++) segtree[i][1] = max_val;

    array<int, 2> p;
    for (int i = 0; i < k; i++)
    {
        // Min
        if (op[i] == 1) p[0] = height[i], p[1] = max_val;
        // Max
        else p[0] = 0, p[1] = height[i];
        update(1, 0, siz - 1, left[i], right[i], p);

        cout << i << "\n";
        for (int i = 1; i < 2 * siz; i++)
        {
            if (__builtin_popcount(i) == 1) cout << "\n";
            cout << segtree[i][0] << " " << segtree[i][1] << "\t";
        }
        cout << endl << endl;
    }

    fnd_answers(1, 0, siz - 1, 0, n - 1);
    for (int i = 0; i < n; i++) finalHeight[i] = output[i];
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 645 ms 52524 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 640 ms 52672 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 661 ms 52564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 656 ms 52644 KB Output isn't correct
2 Halted 0 ms 0 KB -