Submission #366829

#	Time	Username	Problem	Language	Result	Execution time	Memory
366829		KoD	Wall (IOI14_wall)	C++17	100 / 100	1095 ms	89324 KiB

wall

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

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

constexpr int INF = 1000000;

struct SegBeats {
    struct Node {
        int max, smax;
        int min, smin;
        Node(): max(0), smax(-INF), min(0), smin(INF) { }
    };

    Vec<Node> data;
    SegBeats(const int size): data(size * 2) { }

    void fetch(const int k) {
        int l = k * 2;
        int r = k * 2 + 1;
        if (data[l].max < data[r].max) {
            std::swap(l, r);
        }
        data[k].max = data[l].max;
        data[k].smax = std::max(data[l].smax, (data[l].max == data[r].max ? data[r].smax : data[r].max));
        if (data[l].min > data[r].min) {
            std::swap(l, r);
        }
        data[k].min = data[l].min;
        data[k].smin = std::min(data[l].smin, (data[l].min == data[r].min ? data[r].smin : data[r].min));
    }

    void chmax(const int k, const int x) {
        if (x <= data[k].min) {
            return;
        }
        if (data[k].smin <= x) {
            flush(k);
            chmax(k * 2, x);
            chmax(k * 2 + 1, x);
            fetch(k);
        } 
        else {
            upd_min(k, x);
        }
    }

    void chmin(const int k, const int x) {
        if (data[k].max <= x) {
            return;
        }
        if (x <= data[k].smax) {
            flush(k);
            chmin(k * 2, x);
            chmin(k * 2 + 1, x);
            fetch(k);
        }
        else {
            upd_max(k, x);
        }
    }

    void upd_max(const int k, const int x) {
        if (data[k].min == data[k].max) {
            data[k].min = x;
        }
        else if (data[k].smin == data[k].max) {
            data[k].smin = x;
        }
        data[k].max = x;
    }

    void upd_min(const int k, const int x) {
        if (data[k].max == data[k].min) {
            data[k].max = x;
        }
        else if (data[k].smax == data[k].min) {
            data[k].smax = x;
        }
        data[k].min = x;
    }

    void flush(const int k) {
        if (data[k * 2].max > data[k].max) {
            upd_max(k * 2, data[k].max);
        }
        if (data[k * 2 + 1].max > data[k].max) {
            upd_max(k * 2 + 1, data[k].max);
        }
        if (data[k * 2].min < data[k].min) {
            upd_min(k * 2, data[k].min);
        }
        if (data[k * 2 + 1].min < data[k].min) {
            upd_min(k * 2 + 1, data[k].min);
        }
    }

    void push(const int k) {
        const auto lsb = __builtin_ctz(k);
        for (int d = 31 - __builtin_clz(k); d != lsb; --d) {
            flush(k >> d);
        }
    }

    void pull(int k) {
        k >>= __builtin_ctz(k);
        while (k > 1) {
            k >>= 1;
            fetch(k);
        }
    }

    void chmax(int l, int r, const int x) {
        l += size();
        r += size();
        push(l);
        push(r);
        const auto lc = l;
        const auto rc = r;
        while (l < r) {
            if (l & 1) {
                chmax(l, x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                chmax(r, x);
            }   
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    void chmin(int l, int r, const int x) {
        l += size();
        r += size();
        push(l);
        push(r);
        const auto lc = l;
        const auto rc = r;
        while (l < r) {
            if (l & 1) {
                chmin(l, x);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                chmin(r, x);
            }   
            l >>= 1;
            r >>= 1;
        }
        pull(lc);
        pull(rc);
    }

    int get(int i) {
        i += size();
        push(i);
        push(i + 1);
        return data[i].max;
    }

    int size() const {
        return (int) data.size() / 2;
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    SegBeats seg(n);
    for (int i = 0; i < k; ++i) {
        right[i] += 1;
        if (op[i] == 1) {
            seg.chmax(left[i], right[i], height[i]);
        }
        else {
            seg.chmin(left[i], right[i], height[i]);
        }
    }
    for (int i = 0; i < n; ++i) {
        finalHeight[i] = seg.get(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[i] >> left[i] >> right[i] >> height[i];
    }
    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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39