Submission #798030

#	Time	Username	Problem	Language	Result	Execution time	Memory
798030		erray	Wall (IOI14_wall)	C++17	0 / 100	107 ms	21768 KiB

wall

#include "wall.h"
//OMG PINK FLOYD REFERANCE

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi14_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}


struct node {
  int mx = 0, mn = -1;
  void Max(int x) { //turn it to lazy
    if (x >= mn) {
      mn = -1;
    }
    mx = max(x, mx);
  }
  void Min(int x) {
    if (x <= mx) {
      mx = -1;
    }
    if (mn == -1) {
      mn = x;
    }
    mn = min(x, mn);
  }
  bool empty() {
    return mx == -1 && mn == -1;
  }
};
#define def int mid = (l + r) >> 1, rv = (v + (mid - l) * 2)
struct SegTree {
  vector<node> tree;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2 - 1);
  }
  void push_tags(int v, int rv) {
    if (tree[v].mx != -1) {
      tree[v + 1].Max(tree[v].mx);
      tree[rv].Max(tree[v].mx);
    }
    if (tree[v].mn != -1) {
      tree[v + 1].Min(tree[v].mn);
      tree[rv].Min(tree[v].mn);
    }
    tree[v] = node{};
  }  
  void modify(int v, int l, int r, int ll, int rr, bool op, int x) {
    if (l >= ll && rr >= r) {
      (op ? tree[v].Max(x) : tree[v].Min(x));
      return;
    }
    def;
    push_tags(v, rv);
    if (mid > ll) {
      modify(v + 1, l, mid, ll, rr, op, x);
    }
    if (mid < rr) {
      modify(rv, mid, r, ll, rr, op, x);
    } //check closed - open intervals just in-case
  }
  void push(int v, int l, int r, vector<int>& res) {
    debug(l, r, tree[v].mn, tree[v].mx);
    if (l + 1 == r) {
      if (!tree[v].empty()) {
        res[l] = (tree[v].mx == -1 ? tree[v].mn : tree[v].mx);
      }
      return;
    }
    def;
    push_tags(v, rv);
    push(v + 1, l, mid, res);
    push(rv, mid, r, res);
  }
  vector<int> get() {
    vector<int> res(n);
    push(0, 0, n, res);
    return res;
  }
  void modify(int l, int r, bool op, int x) {
    modify(0, 0, n, l, r + 1, op, x);
  }
};


void buildWall(int n, int k, int fuck_op[], int fuck_left[], int fuck_right[], int fuck_height[], int fuck_finalHeight[]){
  auto O = inverse_fuck(fuck_op, k);
  auto L = inverse_fuck(fuck_left, k);
  auto R = inverse_fuck(fuck_right, k);
  auto H = inverse_fuck(fuck_height, k);
  SegTree st(n);
  for (int i = 0; i < k; ++i) {
    debug(L[i], R[i], O[i] == 1, H[i]);
    st.modify(L[i], R[i], O[i] == 1, H[i]);
  }
  auto res = st.get();
  for (int i = 0; i < n; ++i) {
    fuck_finalHeight[i] = res[i];
  }
  return;
}

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