답안 #683630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
683630	2023-01-19T00:34:26 Z	badont	벽 (IOI14_wall)	C++17	100 / 100	1660 ms	160796 KB

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;
}

Compilation message

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.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	440 KB	Output is correct
3	Correct	3 ms	340 KB	Output is correct
4	Correct	12 ms	1108 KB	Output is correct
5	Correct	8 ms	1108 KB	Output is correct
6	Correct	8 ms	1108 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	140 ms	8428 KB	Output is correct
3	Correct	290 ms	5328 KB	Output is correct
4	Correct	870 ms	15608 KB	Output is correct
5	Correct	374 ms	15604 KB	Output is correct
6	Correct	394 ms	15576 KB	Output is correct

Subtask #3

29.0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	2 ms	436 KB	Output is correct
3	Correct	3 ms	312 KB	Output is correct
4	Correct	13 ms	1140 KB	Output is correct
5	Correct	9 ms	1204 KB	Output is correct
6	Correct	11 ms	1204 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	142 ms	8412 KB	Output is correct
9	Correct	277 ms	5280 KB	Output is correct
10	Correct	884 ms	15608 KB	Output is correct
11	Correct	420 ms	15508 KB	Output is correct
12	Correct	385 ms	15616 KB	Output is correct
13	Correct	1 ms	212 KB	Output is correct
14	Correct	148 ms	8520 KB	Output is correct
15	Correct	55 ms	2412 KB	Output is correct
16	Correct	1039 ms	15612 KB	Output is correct
17	Correct	429 ms	15604 KB	Output is correct
18	Correct	439 ms	15716 KB	Output is correct

Subtask #4

39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	3 ms	340 KB	Output is correct
3	Correct	3 ms	308 KB	Output is correct
4	Correct	11 ms	1108 KB	Output is correct
5	Correct	8 ms	1108 KB	Output is correct
6	Correct	11 ms	1108 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	147 ms	8516 KB	Output is correct
9	Correct	333 ms	5268 KB	Output is correct
10	Correct	829 ms	15612 KB	Output is correct
11	Correct	377 ms	15604 KB	Output is correct
12	Correct	388 ms	15540 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	145 ms	8480 KB	Output is correct
15	Correct	60 ms	2508 KB	Output is correct
16	Correct	1066 ms	15616 KB	Output is correct
17	Correct	390 ms	15484 KB	Output is correct
18	Correct	417 ms	15360 KB	Output is correct
19	Correct	1511 ms	160372 KB	Output is correct
20	Correct	1542 ms	160796 KB	Output is correct
21	Correct	1540 ms	160464 KB	Output is correct
22	Correct	1540 ms	160444 KB	Output is correct
23	Correct	1558 ms	160440 KB	Output is correct
24	Correct	1580 ms	160472 KB	Output is correct
25	Correct	1534 ms	160456 KB	Output is correct
26	Correct	1599 ms	160492 KB	Output is correct
27	Correct	1621 ms	160464 KB	Output is correct
28	Correct	1630 ms	160456 KB	Output is correct
29	Correct	1580 ms	160464 KB	Output is correct
30	Correct	1660 ms	160544 KB	Output is correct