Submission #917045

#	Time	Username	Problem	Language	Result	Execution time	Memory
917045		rxlfd314	Wall (IOI14_wall)	C++17	100 / 100	701 ms	120660 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

struct ST {
  vt<int> st_max, st_min, lz;
  ST(int n) {
    st_max.resize(n << 2);
    st_min.resize(n << 2);
    lz.resize(n << 2, -1);
  }
  #define lc i << 1
  #define rc lc | 1
  void push(int i) {
    if (lz[i] < 0)
      return;
    st_max[lc] = st_max[rc] = st_min[lc] = st_min[rc] = lz[lc] = lz[rc] = lz[i];
    lz[i] = -1;
  }
  void pull(int i) {
    st_max[i] = max(st_max[lc], st_max[rc]);
    st_min[i] = min(st_min[lc], st_min[rc]);
  }
  void chmax(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st_max) >> 2;
    if (tl > qr || tr < ql || st_min[i] >= v)
      return;
    if (ql <= tl && tr <= qr && st_max[i] < v)
      st_max[i] = st_min[i] = lz[i] = v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      chmax(ql, qr, v, lc, tl, tm);
      chmax(ql, qr, v, rc, tm+1, tr);
      pull(i);
    }
  }
  void chmin(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st_max) >> 2;
    if (tl > qr || tr < ql || st_max[i] <= v)
      return;
    if (ql <= tl && tr <= qr && st_min[i] > v)
      st_max[i] = st_min[i] = lz[i] = v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      chmin(ql, qr, v, lc, tl, tm);
      chmin(ql, qr, v, rc, tm+1, tr);
      pull(i);
    }
  }
  int qry(int p, int i = 1, int tl = 0, int tr = -1) {
    tr += size(st_max) >> 2;
    while (tl < tr) {
      push(i);
      int tm = tl + tr >> 1;
      if (p <= tm)
        i = lc, tr = tm;
      else
        i = rc, tl = tm + 1;
    }
    return st_max[i];
  }
  #undef lc
  #undef rc
};

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
  ST st(N);
  FOR(i, 0, K-1) {
    if (op[i] == 1)
      st.chmax(left[i], right[i], height[i]);
    else
      st.chmin(left[i], right[i], height[i]);
  }
  FOR(i, 0, N-1)
    finalHeight[i] = st.qry(i);
}

Compilation message (stderr)

wall.cpp: In member function 'void ST::chmax(int, int, int, int, int, int)':
wall.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
wall.cpp: In member function 'void ST::chmin(int, int, int, int, int, int)':
wall.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
wall.cpp: In member function 'int ST::qry(int, int, int, int)':
wall.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |       int tm = tl + tr >> 1;
      |                ~~~^~~~

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