Submission #1076671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076671		juicy	Wall (IOI14_wall)	C++17	100 / 100	1226 ms	69840 KiB

wall

#include "wall.h"

#include <bits/stdc++.h>

namespace {
    const int N = 2e6 + 5, inf = 1e9;

    int n;
    std::array<int, 2> s[4 * N];

    void bld(int id = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            s[id] = {0, 0}; 
            return;
        }
        s[id] = {-inf, inf};
        int md = (l + r) / 2;
        bld(id * 2, l, md);
        bld(id * 2 + 1, md + 1, r);
    }

    void app(int id, int x, int op) {
        for (auto it : {0, 1}) {
            if (op == 2) {
                s[id][it] = std::min(s[id][it], x);
            } else {
                s[id][it] = std::max(s[id][it], x);
            }
        }
    }

    void psh(int id) {
        if (s[id] != std::array<int, 2>{inf, -inf}) {
            for (auto i : {id * 2, id * 2 + 1}) {
                app(i, s[id][0], 1);
                app(i, s[id][1], 2);
            }
            s[id] = {-inf, inf};
        }
    }

    void upd(int u, int v, int x, int op, int id = 1, int l = 0, int r = n - 1) {
        if (u <= l && r <= v) {
            app(id, x, op);
            return;
        }
        psh(id);
        int md = (l + r) / 2;
        if (u <= md) {
            upd(u, v, x, op, id * 2, l, md);
        } 
        if (md < v) {
            upd(u, v, x, op, id * 2 + 1, md + 1, r);
        }
    }

    int qry(int i, int id = 1, int l = 0, int r = n - 1) {
        if (l == r) {
            assert(s[id][0] == s[id][1]);
            return s[id][0];
        }
        psh(id);
        int md = (l + r) / 2;
        return i <= md ? qry(i, id * 2, l, md) : qry(i, id * 2 + 1, md + 1, r);
    }
}

void buildWall(int n, int k, int *op, int *le, int *ri, int *a, int *res) {
    ::n = n;
    bld();
    for (int i = 0; i < k; ++i) {
        upd(le[i], ri[i], a[i], op[i]);
    }
    for (int i = 0; i < n; ++i) {
        res[i] = qry(i);
    }
}

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