Submission #798058

#	Time	Username	Problem	Language	Result	Execution time	Memory
798058		erray	Wall (IOI14_wall)	C++17	100 / 100	590 ms	89036 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;
}


const int inf = int(1e6);
struct node {
  int mx = 0, mn = inf;
  int set = -1;
  void push(node x) {
    if (x.set != -1) {
      set = x.set;
    } else if (set != -1) {
      set = max(set, x.mx);
      set = min(set, x.mn);
    } else {
      if (x.mx >= mn) {
        set = x.mx;
        assert(x.mn > mx);
      } else if (x.mn <= mx) {
        set = x.mn;
      } else {
        mx = max(mx, x.mx);
        mn = min(mn, x.mn);
      }
    }
  }
};
#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) {
    tree[v + 1].push(tree[v]);
    tree[rv].push(tree[v]);
    tree[v] = node{};
  }  
  void modify(int v, int l, int r, int ll, int rr, bool op, int x) {
    if (l >= ll && rr >= r) {
      node add{};
      (op ? add.mx : add.mn) = x;
      tree[v].push(add);
      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) {
      res[l] = (tree[v].set == -1 ? tree[v].mx : tree[v].set);
      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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39