oj.uz

답안 #751873

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
751873 2023-06-01T17:14:10 Z adrilen 벽 (IOI14_wall) C++17
24 / 100
 242 ms 20664 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);
            }
        }
    }

    bool operator==(const Node &right) const
    {
        return (val == right.val) && (empty == right.empty) && (is_max == right.is_max) && (fini == right.fini);
    }
} ;

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 ;

    Node test = segtree[pos];
    test.comp(p);
    if (test == segtree[pos]) 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)
{
    // cout << pos << "\n";
    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;
        // 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 = 1; i < siz; i++) segtree[i].empty = false;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 242 ms 8096 KB Output is correct
3 Correct 106 ms 4072 KB Output is correct
4 Correct 227 ms 20100 KB Output is correct
5 Correct 223 ms 20664 KB Output is correct
6 Correct 242 ms 19044 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Incorrect 2 ms 404 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 460 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -