oj.uz

Submission #683630

# Submission time Handle Problem Language Result Execution time Memory
683630 2023-01-19T00:34:26 Z badont Wall (IOI14_wall) C++17
100 / 100
 1660 ms 160796 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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