Submission #1260895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260895		thecyb	Wall (IOI14_wall)	C++17	0 / 100	134 ms	8008 KiB

wall

/*
    ==                     ==
                 <^\()/^>               <^\()/^>
                  \/  \/                 \/  \/
                   /__\      .  '  .      /__\
      ==            /\    .     |     .    /\            ==
   <^\()/^>       !_\/       '  |  '       \/_!       <^\()/^>
    \/  \/     !_/I_||  .  '   \'/   '  .  ||_I\_!     \/  \/
     /__\     /I_/| ||      -==C++==-      || |\_I\     /__\
     /_ \   !//|  | ||  '  .   /.\   .  '  || |  |\\!   /_ \
    (-   ) /I/ |  | ||       .  |  .       || |  | \I\ (=   )
     \__/!//|  |  | ||    '     |     '    || |  |  |\\!\__/
     /  \I/ |  |  | ||       '  .  '    *  || |  |  | \I/  \
    {_ __}  |  |  | ||                     || |  |  |  {____}
 _!__|= ||  |  |  | ||   *      +          || |  |  |  ||  |__!_
 _I__|  ||__|__|__|_||          A          ||_|__|__|__||- |__I_
 -|--|- ||--|--|--|-||       __/_\__  *    ||-|--|--|--||= |--|-
  |  |  ||  |  |  | ||      /\-'o'-/\      || |  |  |  ||  |  |
  |  |= ||  |  |  | ||     _||:<_>:||_     || |  |  |  ||= |  |
  |  |- ||  |  |  | || *  /\_/=====\_/\  * || |  |  |  ||= |  |
  |  |- ||  |  |  | ||  __|:_:_[I]_:_:|__  || |  |  |  ||- |  |
 _|__|  ||__|__|__|_||:::::::::::::::::::::||_|__|__|__||  |__|_
 -|--|= ||--|--|--|-||:::::::::::::::::::::||-|--|--|--||- |--|-
  jgs|- ||  |  |  | ||:::::::::::::::::::::|| |  |  |  ||= |  |
~~~~~~~~~^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^~~~~~~~~~
*/
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second

struct SegTree {
  std::vector<std::pair<int, int>> tree;
  std::vector<std::pair<int, int>> lazy;
  int sz;
  const std::pair<int, int> identity = {-1, -1};
  SegTree(const int &n) {
    sz = n;
    tree = std::vector<std::pair<int, int>>(sz << 2 | 1, {0, 0});
    lazy = std::vector<std::pair<int, int>>(sz << 2 | 1, identity);
  }

  void apply(const int &id, const std::pair<int, int> &u) {
    if (u.ss == 1) {
      tree[id].ff = std::max(tree[id].ff, u.ff);
      tree[id].ss = std::max(tree[id].ss, tree[id].ff);
    } else {
      tree[id].ss = std::min(tree[id].ss, u.ff);
      tree[id].ff = std::min(tree[id].ff, tree[id].ss);
    }
    lazy[id] = u;
  }

  void push(const int &id) {
    if (lazy[id].ff == -1)
      return;
    apply(id << 1, lazy[id]);
    apply(id << 1 | 1, lazy[id]);
    lazy[id] = {-1, -1};
  }

  std::pair<int, int> combine(const std::pair<int, int> &l,
                              const std::pair<int, int> &r) {
    if (l == identity)
      return r;
    if (r == identity)
      return l;
    return std::make_pair(std::min({l.ff, l.ss, r.ff, r.ss}),
                          std::max({l.ff, l.ss, r.ff, r.ss}));
  }

  void upd(const int &id, const int &l, const int &r, const int &u,
           const int &v, const int &h, const int &t) {
    if (l > v || r < u)
      return;
    if (l >= u && r <= v)
      apply(id, std::make_pair(h, t));
    else {
      push(id);
      int m = (l + r) >> 1;
      upd(id << 1, l, m, u, v, h, t);
      upd(id << 1 | 1, m + 1, r, u, v, h, t);
      tree[id] = combine(tree[id << 1], tree[id << 1 | 1]);
    }
  }

  void upd(const int &l, const int &r, const int &h, const int &type) {
    upd(1, 0, sz - 1, l, r, h, type);
  }

  std::pair<int, int> query(const int &id, const int &l, const int &r,
                            const int &u, const int &v) {
    if (l > v || r < u)
      return identity;
    if (l >= u && r <= v)
      return tree[id];
    push(id);
    int m = (l + r) >> 1;
    return combine(query(id << 1, l, m, u, v),
                   query(id << 1 | 1, m + 1, r, u, v));
  }

  std::pair<int, int> query(const int &l, const int &r) {
    return query(1, 0, sz - 1, l, r);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {
  SegTree st(n);
  for (int i = 0; i < k; i++) {
    st.upd(left[i], right[i], height[i], op[i]);
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = st.query(i, i).ff;
    // std::cout << finalHeight[i] << ' ';
  }
}

// int main() {
//   std::ios_base::sync_with_stdio(false);
//   std::cin.tie(0);
//   std::cout.tie(0);
//   int n, k;
//   std::cin >> n >> k;
//   int op[n], left[n], right[n], height[n];
//   int finalHeight[n];
//   for (int i = 0; i < n; i++)
//     std::cin >> op[i] >> left[i] >> right[i] >> height[i];
//   buildWall(n, k, op, left, right, height, finalHeight);
// }

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