oj.uz

Submission #394792

# Submission time Handle Problem Language Result Execution time Memory
394792 2021-04-27T10:16:48 Z Hegdahl Wall (IOI14_wall) C++17
100 / 100
 941 ms 107732 KB 
#pragma GCC optimize("Ofast")
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#ifdef ENABLE_DEBUG
#include <debug.h>
#else
#define DEBUG(...) do {} while (0)
#endif

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
using lll = __int128;
using ulll = unsigned __int128;

using ld = long double;

template<typename T, size_t N> using ar = array<T, N>;

template<typename T, typename Cmp = less<T>>
using iset = tree<T, null_type, Cmp, rb_tree_tag,
		  tree_order_statistics_node_update, allocator<T>>;

#define REPSI(name, start, stop, step) for (ll name = start; name < (ll)stop; name += step)
#define REPS(name, start, stop) REPSI(name, start, stop, 1)
#define REP(name, stop) REPS(name, 0, stop)

#define RREPSI(name, start, stop, step) for (ll name = stop-1; name >= (ll)start; name -= step)
#define RREPS(name, start, stop) RREPSI(name, start, stop, 1)
#define RREP(name, stop) RREPS(name, 0, stop)

template<typename T> void cins(T &first) { cin >> first; }
template<typename T, typename... Ts> void cins(T &first, T &second, Ts&... rest) {
  cin >> first;
  cins(second, rest...);
}

#define GET(type, ...) type __VA_ARGS__; cins(__VA_ARGS__)
#define GETI(...) GET(int, __VA_ARGS__)
#define GETLL(...) GET(ll, __VA_ARGS__)
#define GETS(...) GET(string, __VA_ARGS__)
#define GETD(...) GET(double, __VA_ARGS__)
#define GETC(...) GET(char, __VA_ARGS__)

struct hsh {
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    x += FIXED_RANDOM;
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
};

template<class S, class F>
struct SegTreeBase {
  
  vector<S> values;
  vector<F> queued;
  int lg2, offset;

  static constexpr int log2i(unsigned n) { return 32-__builtin_clz(--n); }
  SegTreeBase(const vector<S> &src)
    : lg2(log2i((int)src.size())), offset(1<<log2i((int)src.size())) {
    values.reserve(2*offset);
    values.resize(offset);
    values.insert(values.end(), src.begin(), src.end());
    values.resize(2*offset);
    queued.resize(offset);
    for (int i = offset-1; i > 0; --i) recalc(i);
  }

  void recalc(int I) {
    assert(I > 0 && I < offset);
    values[I] = values[2*I] * values[2*I+1];
  }

  void push(int I) {
    assert(I > 0 && I < offset);
    values[2*I] = queued[I] * values[2*I];
    values[2*I+1] = queued[I] * values[2*I+1];
    if (2*I < offset) {
      queued[2*I] = queued[I] * queued[2*I];
      queued[2*I+1] = queued[I] * queued[2*I+1];
    }
    queued[I] = F();
  }

  void push_col(int I) {
    assert(I >= offset && I < 2*offset);
    for (int lvl = lg2-1; lvl >= 0; --lvl)
      push((I>>lvl)/2);
  }

  void push_range(int I, int J) {
    assert(I+1 >= offset && I+1 < 2*offset);
    assert(J-1 >= offset && J-1 < 2*offset);
    assert(I+1 < J);
    for (int lvl = lg2-1; lvl >= 0; --lvl) {
      push(((I+1)>>lvl)/2);
      if (I+1 != J-1) push(((J-1)>>lvl)/2);
    }
  }

  void set(int i, S v) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    values[i] = v;
    while (i /= 2) recalc(i);
  }

  void upd_node(int I, const F &f) {
    assert(I > 0 && I < 2*offset);
    values[I] = f * values[I];
    if (I < offset) queued[I] = f * queued[I];
  }

  void upd(int i, const F &f) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    upd_node(i, f);
    while (i/=2) recalc(i);
  }

  void upd(int i, int j, const F &f) {
    assert(i >= 0 && i < offset);
    assert(j >= 0 && j < offset);
    assert(i <= j);
    i += offset-1;
    j += offset+1;
    int oi = i, oj = j;
    push_range(i, j);
    while (i+1 < j) {
      if ((i&1)==0) upd_node(i+1, f);
      if ((j&1)==1) upd_node(j-1, f);
      i >>= 1, j >>= 1;
    }
    i = oi+1, j = oj-1;
    for (int lvl = 1; lvl <= lg2; lvl++) {
      if (__builtin_ctz(i) < lvl) recalc(i >> lvl);
      if (__builtin_ctz(j+1) < lvl) recalc(j >> lvl);
    }
  }

  S qry(int i) {
    assert(i >= 0 && i < offset);
    i += offset;
    push_col(i);
    return values[i];
  }

  S qry(int i, int j) {
    assert(i >= 0 && i < offset);
    assert(j >= 0 && j < offset);
    assert(i <= j);
    i += offset-1;
    j += offset+1;
    push_range(i, j);
    S ls, rs;
    while (i+1 < j) {
      if ((i&1)==0) ls = ls * values[i+1];
      if ((j&1)==1) rs = values[j-1] * rs;
      i >>= 1, j >>= 1;
    }
    return ls * rs;
  }

  template<class Cmp>
  int upper_bound(S t, Cmp cmp) {
    if (cmp(values[1], t)) return offset;
    int lvl = lg2;
    int I = 1;
    S pre;
    while (lvl--) {
      I *= 2;
      push(I/2);
      if (cmp(pre*values[I], t)) {
        pre = pre*values[I];
        ++I;
      }
    }
    return I - offset;
  }

};

struct S {
  ll v = 0;
  S operator*(const S &rhs) const { return *this; }
};

const ll INF = 1LL<<60;

struct F {
  ll mn = INF;
  ll mx = -INF;
  F operator*(const F &rhs) const {
    F ret = rhs;
    ret.mn = min(ret.mn, mn);
    ret.mx = min(ret.mx, mn);
    ret.mn = max(ret.mn, mx);
    ret.mx = max(ret.mx, mx);
    assert(ret.mn >= ret.mx);
    return ret;
  }
  S operator*(const S &rhs) const {
    return {min(max(rhs.v, mx), mn)};
  }
};

using SegTree = SegTreeBase<S, F>;

void buildWall(int n, int q, int op[], int left[], int right[], int height[], int finalHeight[]) {
  vector<S> src(n);
  SegTree st(src);

  REP(qq, q) {
    int i = left[qq];
    int j = right[qq];
    int h = height[qq];
    if (op[qq] == 1) {
      st.upd(i, j, {INF, h});
    } else if (op[qq] == 2) {
      st.upd(i, j, {h, -INF});
    } else assert(false);
  }

  REPS(I, 1, st.offset) st.push(I);

  REP(i, n) finalHeight[i] = st.values[st.offset+i].v;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 7 ms 1100 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 6 ms 1072 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 166 ms 13860 KB Output is correct
3 Correct 206 ms 8480 KB Output is correct
4 Correct 596 ms 23016 KB Output is correct
5 Correct 453 ms 23564 KB Output is correct
6 Correct 484 ms 21988 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 3 ms 336 KB Output is correct
4 Correct 9 ms 1112 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 9 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 169 ms 13940 KB Output is correct
9 Correct 231 ms 8580 KB Output is correct
10 Correct 590 ms 23004 KB Output is correct
11 Correct 484 ms 23564 KB Output is correct
12 Correct 484 ms 22000 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 174 ms 13928 KB Output is correct
15 Correct 34 ms 2520 KB Output is correct
16 Correct 658 ms 23008 KB Output is correct
17 Correct 491 ms 22436 KB Output is correct
18 Correct 467 ms 22436 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 8 ms 1076 KB Output is correct
5 Correct 6 ms 1100 KB Output is correct
6 Correct 6 ms 1100 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 183 ms 13964 KB Output is correct
9 Correct 208 ms 8516 KB Output is correct
10 Correct 574 ms 22956 KB Output is correct
11 Correct 497 ms 23492 KB Output is correct
12 Correct 447 ms 21996 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 180 ms 14068 KB Output is correct
15 Correct 35 ms 2532 KB Output is correct
16 Correct 600 ms 23064 KB Output is correct
17 Correct 457 ms 22468 KB Output is correct
18 Correct 453 ms 22468 KB Output is correct
19 Correct 900 ms 107704 KB Output is correct
20 Correct 876 ms 107704 KB Output is correct
21 Correct 925 ms 107648 KB Output is correct
22 Correct 880 ms 107692 KB Output is correct
23 Correct 931 ms 107696 KB Output is correct
24 Correct 881 ms 107732 KB Output is correct
25 Correct 866 ms 107672 KB Output is correct
26 Correct 902 ms 107716 KB Output is correct
27 Correct 881 ms 107732 KB Output is correct
28 Correct 901 ms 107696 KB Output is correct
29 Correct 941 ms 107708 KB Output is correct
30 Correct 886 ms 107696 KB Output is correct