Submission #1260908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260908		thecyb	Wall (IOI14_wall)	C++17	100 / 100	884 ms	78692 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;
  int sz;
  const std::pair<int, int> identity = {0, INT_MAX};
  SegTree(const int &n) {
    sz = n;
    tree = std::vector<std::pair<int, int>>(sz << 2 | 1, identity);
  }

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

  void push(const int &id) {
    apply(id << 1, tree[id]);
    apply(id << 1 | 1, tree[id]);
    tree[id] = identity;
  }

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

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

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

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

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++) {
    if (op[i] == 1)
      st.upd(left[i], right[i], {height[i], INT_MAX});
    else
      st.upd(left[i], right[i], {0, height[i]});
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = st.query(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: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39