Submission #916996

#	Time	Username	Problem	Language	Result	Execution time	Memory
916996		agusss	3D Histogram (COCI20_histogram)	C++17	0 / 110	1 ms	348 KiB

histogram

#include "vector"
#include "stack"
#include "iostream"
#include <algorithm>


using namespace std;


struct Type { int v; };

struct SegmentTree {

  struct NodeType { int l, r, min; };

  NodeType merge_nodes(NodeType a, NodeType b) {
    return { a.l, b.r, min(a.min, b.min) };
  };

  NodeType set_leaf(int i, Type a) {
    return { i, i, a.v };
  }

  vector<NodeType> tree;

  vector<Type> *array;

  int left(int index) { return (index << 1) + 1; }

  int right(int index) { return (index << 1) + 2; }

  int mid(int l, int r) { return (l + r) >> 1; }

  bool on_left(NodeType a, int i) { return i <= mid(a.l, a.r); }

  void _build(int index, int l, int r) {
    if (l == r) {
      tree[index] = set_leaf(l, (*array)[l]); 
    } else {
      _build(left(index), l, mid(l, r));
      _build(right(index), mid(l, r) + 1, r);
      tree[index] = merge_nodes(tree[left(index)], tree[right(index)]);
    }
  }

  void build(vector<Type> &A) {
    array = &A;
    tree.resize((*array).size() * 4);
    _build(0, 0, (*array).size() - 1);
  }

  int u_i;

  Type u_v;

  void _update(int index) {
    if (tree[index].l == tree[index].r) {
      tree[index] = set_leaf(u_i, u_v);
      (*array)[u_i] = u_v;
    } else {
      if (on_left(tree[index], u_i)) {
        _update(left(index));
      } else {
        _update(right(index));
      }
      tree[index] = merge_nodes(tree[left(index)], tree[right(index)]);
    }
  }

  void update(int i, Type v) {
    u_i = i;
    u_v = v;
    _update(0);
  }

  int q_l;
  
  int q_r;
  
  NodeType _query(int index) {
    if (q_l <= tree[index].l and tree[index].r <= q_r) {
      return tree[index];
    }
    if (on_left(tree[index], q_r)) {
      return _query(left(index));
    }
    if (!on_left(tree[index], q_l)) {
      return _query(right(index));
    }
    return merge_nodes(_query(left(index)), _query(right(index))); 
  }

  NodeType query(int l, int r) {
    q_l = l;
    q_r = r;
    return _query(0);
  }
};

long long largestRectangleArea(vector<int>& heights, vector<Type> &h2) {
  int n = heights.size();
  int left_smaller[n];
  int right_smaller[n];
  stack<int> s;
  int i = 0;
  while (i < n) {
    while (!s.empty() && heights[s.top()] >= heights[i]) {
      s.pop();
    }
    if (i > 0 && heights[i] == heights[i - 1]) {
      left_smaller[i] = left_smaller[i - 1];
    } else {
      left_smaller[i] = s.empty() ? -1 : s.top();
    }
    s.push(i);
    i++;
  }
  s = stack<int>();
  i = n - 1;
  while (i >= 0) {
    // TODO create test cases to WA for only >
    while (!s.empty() && heights[s.top()] >= heights[i]) {
      s.pop();
    }
    if (i + 1 < n && heights[i] == heights[i + 1]) {
      right_smaller[i] = right_smaller[i + 1];
    } else {
      right_smaller[i] = s.empty() ? n : s.top();
    }
    s.push(i);
    i--;
  }
  //for (int i = 0; i < n; i++) cout << left_smaller[i] << ", "; cout << "\n";
  //for (int i = 0; i < n; i++) cout << right_smaller[i] << ", "; cout << "\n";
  long long max_area = 0;
  SegmentTree st;
  st.build(h2);
  for (int i = 0; i < n; i ++) {
    long long area = (long long)heights[i] * (long long)(right_smaller[i] - left_smaller[i] - 1);
    auto [ _, __, x ] = st.query(left_smaller[i] + 1, right_smaller[i] -1);
    max_area = max(max_area, area * x);
  }
  return max_area;
}


int main() {

  int n, x, y;
  while(scanf("%d\n", &n) != EOF) {
    vector<int> A;
    vector<Type> B;
    for (int i = 0; i < n; i++) {
      if (scanf("%d %d", &x, &y)) ;
      A.push_back(x);
      B.push_back({ y });
    }
    printf("%lld\n", largestRectangleArea(A, B));
  }
  return 0;
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 90