제출 #683630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683630		badont	벽 (IOI14_wall)	C++17	100 / 100	1660 ms	160796 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }

#ifdef LOCAL
#define debug(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define debug(...) "zzz"
#endif

using LL = long long;
using LD = long double;
using pii = pair<LL,LL>;

#define FOR(i, n) for(int i = 1; i<=n; i++)
#define F0R(i, n) for(int i = 0; i<n; i++)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second

template<typename T, typename = void> struct is_iterable : false_type {};
template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
  cout << "["; 
  for (auto it = v.begin(); it != v.end();) {
    cout << *it;
    if (++it != v.end()) cout << ", ";
  }
  return cout << "]";
}

//var 
LL T;

const int INF = 1e9;
struct Info {
  int L; int R;
  Info() : L(-INF), R(INF) {}
  Info(int L, int r) : L(L), R(R) {}
  Info(int a) : L(a), R(a) {}

  bool operator==(const Info& o) const {
    return this->L == o.L && this->R == o.R;
  }

  Info& operator+=(const Info& o) {
    if (o.L > this->R) {
      this->L = this->R = o.L;
    } else if (o.R < this->L) {
      this->R = this->L = o.R;
    } else {
      this->L = max(this->L, o.L);
      this->R = min(this->R, o.R);
    }

    return *this;
  };
};

const Info bad = {-INF, -INF};

struct Merge {
  Info operator()(const Info& a, const Info& b) {
    if (a == bad) return b;
    if (b == bad) return a;


    Info ret;
    ret.L = min(a.L, b.L);
    ret.R = max(a.R, b.R);
    return ret;
  }
};

template<typename T, typename Merge = plus<T>, typename LazyOp=LL>
struct lazy_seg {
  int n;
  vector<T> tr;
  vector<LazyOp> lazy_inc;
  vector<bool> tag_inc;
  Merge merge;
  
  void pull(int z) {
    tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
  };
  
  lazy_seg(int n) : n(n), tr(4 * n + 5), lazy_inc(4 * n + 5), tag_inc(4 * n + 5), merge(Merge()) {}
  
  lazy_seg(vector<int> a) : lazy_seg((int)a.size()) {
    function<void (int, int, int)> build = [&](int z, int l, int r) {
      if (l == r) {
        tr[z] = T(a[l]);
        return;
      }
      int m = (l + r) >> 1;
      build(2 * z, l, m);
      build(2 * z + 1, m + 1, r);
      pull(z);
    };
    build(1, 0, n - 1);
  }
  
  
  void push(int z, int l, int r) {
    if (tag_inc[z]) {
      tr[z] += lazy_inc[z];
      //debug(z, l, r, tr[z].L, tr[z].R);
      if (l < r) F0R (i, 2) {       
        lazy_inc[2 * z + i] += lazy_inc[z];
        tag_inc[2 * z + i] = true;
      }
    }
    tag_inc[z] = false;
    lazy_inc[z] = LazyOp();
  }
  
  void up_inc(int z, int l, int r, int ql, int qr, const LazyOp& val) {
    push(z, l, r);
        if (ql > qr) return;        
    if (ql == l && qr == r) {
      lazy_inc[z] += val;
      tag_inc[z] = true;
      push(z, l, r); 
      return;
    } 
    int m = (l + r) >> 1;
    up_inc(2 * z, l, m, ql, min(qr, m), val);
    up_inc(2 * z + 1, m + 1, r, max(ql, m + 1), qr, val);
    pull(z);
  };

  T query(int z, int l, int r, int ql, int qr) {
    push(z, l, r);
        if (ql > qr) return bad;
    if (ql == l && qr == r) {
      return tr[z];
    }
    int m = (l + r) >> 1;
    return merge(
      query(2 * z, l, m, ql, min(qr, m)),
      query(2 * z + 1, m + 1, r, max(ql, m + 1), qr)
    );
  };
  
  void up_inc(int l, int r, const LazyOp& val) { return up_inc(1, 0, n - 1, l, r, val); }
  T query(int l, int r) { return query(1, 0, n - 1, l, r); }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  vector<int> a(n, 0);

  lazy_seg<Info, Merge, Info> tree(a);
  F0R (i, k) {
    int T = op[i], l = left[i], r = right[i], h = height[i];
    Info val;
    if (T == 1) val.L = h;
    else val.R = h;
    tree.up_inc(l, r, val);
  }

  F0R (i, n) {
    finalHeight[i] = tree.query(i,i).L;
  }

  return;
}

컴파일 시 표준 에러 (stderr) 메시지

wall.cpp: In constructor 'Info::Info(int, int)':
wall.cpp:47:3: warning: 'Info::R' is initialized with itself [-Winit-self]
   47 |   Info(int L, int r) : L(L), R(R) {}
      |   ^~~~
wall.cpp: In constructor 'Info::Info(int, int)':
wall.cpp:47:32: warning: '*<unknown>.Info::R' is used uninitialized in this function [-Wuninitialized]
   47 |   Info(int L, int r) : L(L), R(R) {}
      |                                ^

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