Submission #366742

#	Time	Username	Problem	Language	Result	Execution time	Memory
366742		KoD	Wall (IOI14_wall)	C++17	0 / 100	169 ms	13940 KiB

wall

#ifndef __APPLE__
#include "wall.h"
#endif
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct Segtree {
    Vec<std::pair<int, bool>> data;
    Segtree(const int n): data(2 * n) { }
    void flush(const int k) {
        if (data[k].second) {
            data[k * 2] = data[k];
            data[k * 2 + 1] = data[k];
            data[k].first = 0;
            data[k].second = false;
        }
    }
    void push(const int k) {
        for (int d = 31 - __builtin_clz(k); d > 0; d--) {
            flush(k >> d);
        }
    }
    void apply(const int k, const int v, const bool max) {
        if (data[k].second) {
            data[k].first = (max ? std::max(data[k].first, v) : std::min(data[k].first, v));
        }
        else {
            data[k].first = v;
            data[k].second = true;
        }
    }
    void operate(int l, int r, const int v, const bool max) {
        l += size();
        r += size();
        push(l);
        push(r);
        while (l < r) {
            if (l & 1) {
                apply(l, v, max);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                apply(r, v, max);
            }
            l >>= 1;
            r >>= 1;
        }
    }
    int size() {
        return (int) data.size() / 2;
    }
    Vec<int> calc() {
        for (int i = 1; i < size(); ++i) {
            flush(i);
        }
        Vec<int> ret(size());
        for (int i = 0; i < size(); ++i) {
            ret[i] = data[i + size()].first;
        }
        return ret;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    Segtree seg(n);
    for (int i = 0; i < k; ++i) {
        seg.operate(left[i], right[i] + 1, height[i], op[i] == 1);
    }
    const auto ans = seg.calc();
    for (int i = 0; i < n; ++i) {
        finalHeight[i] = ans[i];
    }
}

#ifdef __APPLE__
int op[100];
int left[100];
int right[100];
int height[100];
int finalHeight[100];

int main() {
    int n, k;
    std::cin >> n >> k;
    for (int i = 0; i < k; ++i) {
        std::cin >> op[k] >> left[k] >> right[k] >> height[k];
    }
    buildWall(n, k, op, left, right, height, finalHeight);
    for (int i = 0; i < n; ++i) {
        std::cout << finalHeight[i] << " \n"[i + 1 == n];
    }
    return 0;
}
#endif

• Subtask 1: 0 / 8
• Subtask 2: 0 / 24
• Subtask 3: 0 / 29
• Subtask 4: 0 / 39