Submission #700385

#	Time	Username	Problem	Language	Result	Execution time	Memory
700385		Cyanmond	Wall (IOI14_wall)	C++17	8 / 100	3083 ms	16172 KiB

wall

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

constexpr int inf = 500000;

struct node {
    int l;
    int r;
    // clamp(a, l, r)
};
node merge(node a, node b) {
    a.l = std::min(b.r, a.l);
    a.r = std::min(b.r, a.r);
    a.l = std::max(b.l, a.l);
    a.r = std::max(b.l, a.r);
    return a;
}
node id = {-inf, inf};

int eval(int x, node p) {
    return std::max(p.l, std::min(p.r, x));
}

class segtree {

};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
    std::vector<std::vector<int>> addList(n + 1), eraseList(n + 1);
    for (int i = 0; i < k; ++i) {
        addList[left[i]].push_back(i);
        eraseList[right[i] + 1].push_back(i);
    }
    std::vector<node> queries(k, id);
    for (int i = 0; i < n; ++i) {
        for (const int x : addList[i]) {
            if (op[x] == 1) {
                queries[x] = {height[x], inf};
            } else {
                queries[x] = {-inf, height[x]};
            }
        }
        for (const int x : eraseList[i]) {
            queries[x] = id;
        }

        node res = id;
        for (int j = 0; j < k; ++j) {
            res = merge(res, queries[j]);
        }
        finalHeight[i] = eval(0, res);
    }
}

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