Submission #492821

#	Time	Username	Problem	Language	Result	Execution time	Memory
492821		boykut	Wall (IOI14_wall)	C++14	100 / 100	1116 ms	86344 KiB

wall

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

using namespace std;

template <typename T>
class segment_tree {
private:
  struct node {
    T min, max;
  };
  int n;
  vector<node> t;
  void push(int v, int vl, int vr) {
    if (vl == vr) return;
    t[2 * v + 1].min = ::max(t[v].min, ::min(t[2 * v + 1].min, t[v].max));
    t[2 * v + 1].max = ::min(t[v].max, ::max(t[2 * v + 1].max, t[v].min));
    t[2 * v + 2].min = ::max(t[v].min, ::min(t[2 * v + 2].min, t[v].max));
    t[2 * v + 2].max = ::min(t[v].max, ::max(t[2 * v + 2].max, t[v].min));
    t[v].min = 0; t[v].max = LLONG_MAX;
  }
  T get(int i, int v, int vl, int vr) {
    push(v, vl, vr);
    if (vl == vr) {
      return t[v].min;
    } else {
      int vm = (vl + vr) / 2;
      if (i <= vm)
        return get(i, 2 * v + 1, vl, vm);
      else
        return get(i, 2 * v + 2, vm + 1, vr);
    }
  }
  void update(int l, int r, T x, int v, int vl, int vr, int type) {
    push(v, vl, vr);
    if (l > vr || vl > r)
      return;
    if (l <= vl && vr <= r) {
      if (type == 1) {
        t[v].min = ::max(t[v].min, x);
        t[v].max = ::max(t[v].max, x);
      } else {
        t[v].min = ::min(t[v].min, x);
        t[v].max = ::min(t[v].max, x);
      }
    } else {
      int vm = (vl + vr) / 2;
      update(l, r, x, 2 * v + 1, vl, vm, type);
      update(l, r, x, 2 * v + 2, vm + 1, vr, type);
    }
  }
public:
  segment_tree(int k) {
    n = 1; while (n < k) n <<= 1;
    t = vector<node> (2 * n - 1, {0, LLONG_MAX});
  }
  T get(int i) {
    return get(i, 0, 0, n - 1);
  }
  void update(int l, int r, T x, int type) {
    update(l, r, x, 0, 0, n - 1, type);
  }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
  segment_tree<long long> st(n);
  for (int i = 0; i < k; i++) {
      st.update(l[i], r[i], h[i], op[i]);
  }
  for (int i = 0; i < n; i++) {
    ans[i] = st.get(i);
  }
  return;
}

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