Submission #1210218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210218		madamadam3	Wall (IOI14_wall)	C++20	100 / 100	679 ms	78700 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
using ll = long long;

struct SegmentTree {
    int n;
    vector<int> arr, treeMin, treeMax; // lower bound on value, upper bound on value

    void build(int i, int l, int r) {
        if (l + 1 == r) {
          treeMin[i] = treeMax[i] = arr[l];
          return;
        }

        int m = l + (r - l) / 2;
        build(2 * i + 1, l, m);
        build(2 * i + 2, m, r);

        treeMin[i] = max(treeMin[2*i+1], treeMin[2*i+2]);
        treeMax[i] = min(treeMax[2*i+1], treeMax[2*i+2]);
    }

    void apply_update(int i, int minV, int maxV) {
        treeMin[i] = max(treeMin[i], minV);
        treeMax[i] = max(treeMax[i], treeMin[i]);

        treeMax[i] = min(treeMax[i], maxV);
        treeMin[i] = min(treeMin[i], treeMax[i]);
    }

    void push_down(int i) {
        apply_update(2 * i + 1, treeMin[i], treeMax[i]);
        apply_update(2 * i + 2, treeMin[i], treeMax[i]);

        treeMin[i] = 0;
        treeMax[i] = INT_MAX;
    }

    int query(int i, int l, int r, int idx) {
        if (l + 1 == r) return treeMin[i];
        push_down(i);
        int m = l + (r - l) / 2;
        return (idx < m) ? query(2*i+1, l, m, idx) : query(2*i+2, m, r, idx);
    }

    void update(int i, int l, int r, int uL, int uR, int uMin, int uMax) {
        if (r <= uL || uR <= l) return;
        if (uL <= l && r <= uR) {
            apply_update(i, uMin, uMax);
            return;
        }

        push_down(i);
        int m = l + (r - l) / 2;
        update(2 * i + 1, l, m, uL, uR, uMin, uMax);
        update(2 * i + 2, m, r, uL, uR, uMin, uMax);
    }

    SegmentTree(int n) {
        this->n = n;
        this->treeMin.assign(4 * n, 0);
        this->treeMax.assign(4 * n, INT_MAX);

        // build(0, 0, n);
    }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  auto st = SegmentTree(n);

  for (int i = 0; i < k; i++) {
    if (op[i] == 1) { // add
      st.update(0, 0, n, left[i], right[i]+1, height[i], INT_MAX);
    } else if (op[i] == 2) {
      st.update(0, 0, n, left[i], right[i]+1, 0, height[i]);
    }

  }

  for (int i = 0; i < n; i++) {
    // finalHeight[i] = query_sum(i, i);
    finalHeight[i] = st.query(0, 0, n, i);
  }

  return;
}

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