Submission #683627

#	Time	Username	Problem	Language	Result	Execution time	Memory
683627		badont	Wall (IOI14_wall)	C++17	Compilation error	0 ms	0 KiB

wall

#include "wall.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 LL INF = 1e9;
struct Info {
  LL L; LL R;
  Info() : L(-INF), R(INF) {}
  Info(LL L, LL r) : L(L), R(R) {}
  Info(LL 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<LL> 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) {
    LL 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;
}

Compilation message (stderr)

wall.cpp: In function 'void dbg_out()':
wall.cpp:5:18: error: 'cout' was not declared in this scope
    5 | void dbg_out() { cout << endl; }
      |                  ^~~~
wall.cpp:2:1: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
    1 | #include "wall.h"
  +++ |+#include <iostream>
    2 | 
wall.cpp:5:26: error: 'endl' was not declared in this scope
    5 | void dbg_out() { cout << endl; }
      |                          ^~~~
wall.cpp:2:1: note: 'std::endl' is defined in header '<ostream>'; did you forget to '#include <ostream>'?
    1 | #include "wall.h"
  +++ |+#include <ostream>
    2 | 
wall.cpp: In function 'void dbg_out(Head, Tail ...)':
wall.cpp:6:77: error: 'cout' was not declared in this scope
    6 | template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
      |                                                                             ^~~~
wall.cpp:6:77: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
wall.cpp: At global scope:
wall.cpp:16:13: error: 'pair' does not name a type
   16 | using pii = pair<LL,LL>;
      |             ^~~~
wall.cpp:26:71: error: expected class-name before '{' token
   26 | template<typename T, typename = void> struct is_iterable : false_type {};
      |                                                                       ^
wall.cpp:27:44: error: 'void_t' was not declared in this scope
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                            ^~~~~~
wall.cpp:2:1: note: 'std::void_t' is defined in header '<type_traits>'; did you forget to '#include <type_traits>'?
    1 | #include "wall.h"
  +++ |+#include <type_traits>
    2 | 
wall.cpp:27:66: error: 'declval' was not declared in this scope
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                  ^~~~~~~
wall.cpp:2:1: note: 'std::declval' is defined in header '<utility>'; did you forget to '#include <utility>'?
    1 | #include "wall.h"
  +++ |+#include <utility>
    2 | 
wall.cpp:27:60: error: there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available [-fpermissive]
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                            ^~~~~
wall.cpp:27:60: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
wall.cpp:27:66: error: 'declval' was not declared in this scope
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                  ^~~~~~~
wall.cpp:27:66: note: 'std::declval' is defined in header '<utility>'; did you forget to '#include <utility>'?
wall.cpp:27:75: error: expected primary-expression before '>' token
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                           ^
wall.cpp:27:77: error: expected primary-expression before ')' token
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                             ^
wall.cpp:27:60: error: there are no arguments to 'begin' that depend on a template parameter, so a declaration of 'begin' must be available [-fpermissive]
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                            ^~~~~
wall.cpp:27:108: error: template argument 2 is invalid
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                                                            ^~
wall.cpp:27:123: error: expected class-name before '{' token
   27 | template<typename T> struct is_iterable<T, void_t<decltype(begin(declval<T>())),decltype(end(declval<T>()))>> : true_type {};
      |                                                                                                                           ^
wall.cpp:28:31: error: expected nested-name-specifier before 'enable_if'
   28 | template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
      |                               ^~~~~~~~~
wall.cpp:28:40: error: expected initializer before '<' token
   28 | template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v);
      |                                        ^
wall.cpp:29:34: error: 'ostream' does not name a type
   29 | template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
      |                                  ^~~~~~~
wall.cpp:30:31: error: expected nested-name-specifier before 'enable_if'
   30 | template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
      |                               ^~~~~~~~~
wall.cpp:30:40: error: expected initializer before '<' token
   30 | template<typename T> typename enable_if<is_iterable<T>::value&&!is_same<T, string>::value,ostream&>::type operator<<(ostream &cout, T const &v) {
      |                                        ^
wall.cpp: In constructor 'Info::Info(LL, LL)':
wall.cpp:46:3: warning: 'Info::R' is initialized with itself [-Winit-self]
   46 |   Info(LL L, LL r) : L(L), R(R) {}
      |   ^~~~
wall.cpp: In member function 'Info& Info::operator+=(const Info&)':
wall.cpp:59:17: error: 'max' was not declared in this scope
   59 |       this->L = max(this->L, o.L);
      |                 ^~~
wall.cpp:60:17: error: 'min' was not declared in this scope
   60 |       this->R = min(this->R, o.R);
      |                 ^~~
wall.cpp: In member function 'Info Merge::operator()(const Info&, const Info&)':
wall.cpp:76:13: error: 'min' was not declared in this scope
   76 |     ret.L = min(a.L, b.L);
      |             ^~~
wall.cpp:77:13: error: 'max' was not declared in this scope
   77 |     ret.R = max(a.R, b.R);
      |             ^~~
wall.cpp: At global scope:
wall.cpp:82:39: error: 'plus' does not name a type
   82 | template<typename T, typename Merge = plus<T>, typename LazyOp=LL>
      |                                       ^~~~
wall.cpp:82:43: error: expected '>' before '<' token
   82 | template<typename T, typename Merge = plus<T>, typename LazyOp=LL>
      |                                           ^
wall.cpp:85:3: error: 'vector' does not name a type
   85 |   vector<T> tr;
      |   ^~~~~~
wall.cpp:86:3: error: 'vector' does not name a type
   86 |   vector<LazyOp> lazy_inc;
      |   ^~~~~~
wall.cpp:87:3: error: 'vector' does not name a type
   87 |   vector<bool> tag_inc;
      |   ^~~~~~
wall.cpp:96:18: error: expected ')' before '<' token
   96 |   lazy_seg(vector<LL> a) : lazy_seg((int)a.size()) {
      |           ~      ^
      |                  )
wall.cpp:124:58: error: 'LazyOp' does not name a type
  124 |   void up_inc(int z, int l, int r, int ql, int qr, const LazyOp& val) {
      |                                                          ^~~~~~
wall.cpp:152:35: error: 'LazyOp' does not name a type
  152 |   void up_inc(int l, int r, const LazyOp& val) { return up_inc(1, 0, n - 1, l, r, val); }
      |                                   ^~~~~~
wall.cpp: In member function 'void lazy_seg<T, Merge>::pull(int)':
wall.cpp:91:5: error: 'tr' was not declared in this scope
   91 |     tr[z] = merge(tr[2 * z], tr[2 * z + 1]);
      |     ^~
wall.cpp: In constructor 'lazy_seg<T, Merge>::lazy_seg(int)':
wall.cpp:94:27: error: class 'lazy_seg<T, Merge>' does not have any field named 'tr'
   94 |   lazy_seg(int n) : n(n), tr(4 * n + 5), lazy_inc(4 * n + 5), tag_inc(4 * n + 5), merge(Merge()) {}
      |                           ^~
wall.cpp:94:42: error: class 'lazy_seg<T, Merge>' does not have any field named 'lazy_inc'
   94 |   lazy_seg(int n) : n(n), tr(4 * n + 5), lazy_inc(4 * n + 5), tag_inc(4 * n + 5), merge(Merge()) {}
      |                                          ^~~~~~~~
wall.cpp:94:63: error: class 'lazy_seg<T, Merge>' does not have any field named 'tag_inc'
   94 |   lazy_seg(int n) : n(n), tr(4 * n + 5), lazy_inc(4 * n + 5), tag_inc(4 * n + 5), merge(Merge()) {}
      |                                                               ^~~~~~~
wall.cpp: In member function 'void lazy_seg<T, Merge>::push(int, int, int)':
wall.cpp:112:9: error: 'tag_inc' was not declared in this scope
  112 |     if (tag_inc[z]) {
      |         ^~~~~~~
wall.cpp:113:7: error: 'tr' was not declared in this scope; did you mean 'r'?
  113 |       tr[z] += lazy_inc[z];
      |       ^~
      |       r
wall.cpp:113:16: error: 'lazy_inc' was not declared in this scope
  113 |       tr[z] += lazy_inc[z];
      |                ^~~~~~~~
wall.cpp:120:5: error: 'tag_inc' was not declared in this scope
  120 |     tag_inc[z] = false;
      |     ^~~~~~~
wall.cpp:121:5: error: 'lazy_inc' was not declared in this scope
  121 |     lazy_inc[z] = LazyOp();
      |     ^~~~~~~~
wall.cpp:121:19: error: there are no arguments to 'LazyOp' that depend on a template parameter, so a declaration of 'LazyOp' must be available [-fpermissive]
  121 |     lazy_inc[z] = LazyOp();
      |                   ^~~~~~
wall.cpp: In member function 'void lazy_seg<T, Merge>::up_inc(int, int, int, int, int, const int&)':
wall.cpp:128:7: error: 'lazy_inc' was not declared in this scope
  128 |       lazy_inc[z] += val;
      |       ^~~~~~~~
wall.cpp:129:7: error: 'tag_inc' was not declared in this scope
  129 |       tag_inc[z] = true;
      |       ^~~~~~~
wall.cpp:134:29: error: there are no arguments to 'min' that depend on a template parameter, so a declaration of 'min' must be available [-fpermissive]
  134 |     up_inc(2 * z, l, m, ql, min(qr, m), val);
      |                             ^~~
wall.cpp:135:33: error: there are no arguments to 'max' that depend on a template parameter, so a declaration of 'max' must be available [-fpermissive]
  135 |     up_inc(2 * z + 1, m + 1, r, max(ql, m + 1), qr, val);
      |                                 ^~~
wall.cpp: In member function 'T lazy_seg<T, Merge>::query(int, int, int, int, int)':
wall.cpp:143:14: error: 'tr' was not declared in this scope; did you mean 'r'?
  143 |       return tr[z];
      |              ^~
      |              r
wall.cpp:147:30: error: there are no arguments to 'min' that depend on a template parameter, so a declaration of 'min' must be available [-fpermissive]
  147 |       query(2 * z, l, m, ql, min(qr, m)),
      |                              ^~~
wall.cpp:148:34: error: there are no arguments to 'max' that depend on a template parameter, so a declaration of 'max' must be available [-fpermissive]
  148 |       query(2 * z + 1, m + 1, r, max(ql, m + 1), qr)
      |                                  ^~~
wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:157:3: error: 'vector' was not declared in this scope
  157 |   vector<int> a(n, 0);
      |   ^~~~~~
wall.cpp:2:1: note: 'std::vector' is defined in header '<vector>'; did you forget to '#include <vector>'?
    1 | #include "wall.h"
  +++ |+#include <vector>
    2 | 
wall.cpp:157:10: error: expected primary-expression before 'int'
  157 |   vector<int> a(n, 0);
      |          ^~~
wall.cpp:159:29: error: wrong number of template arguments (3, should be at least 1)
  159 |   lazy_seg<Info, Merge, Info> tree(a);
      |                             ^
wall.cpp:83:8: note: provided for 'template<class T, class Merge> struct lazy_seg'
   83 | struct lazy_seg {
      |        ^~~~~~~~
wall.cpp:159:36: error: 'a' was not declared in this scope
  159 |   lazy_seg<Info, Merge, Info> tree(a);
      |                                    ^
wall.cpp:165:10: error: request for member 'up_inc' in 'tree', which is of non-class type 'int'
  165 |     tree.up_inc(l, r, val);
      |          ^~~~~~
wall.cpp:169:27: error: request for member 'query' in 'tree', which is of non-class type 'int'
  169 |     finalHeight[i] = tree.query(i,i).L;
      |                           ^~~~~