Submission #257416

#	Time	Username	Problem	Language	Result	Execution time	Memory
257416		KoD	Land of the Rainbow Gold (APIO17_rainbow)	C++17	12 / 100	652 ms	43004 KiB

rainbow

#line 1 "main.cpp"

/**
 * @title Template
 */

#line 1 "rainbow.h"

#ifdef LOCAL
#ifndef __RAINBOW_H
#define __RAINBOW_H

#include <cstdint>

void init(int32_t R, int32_t C, int32_t sr, int32_t sc, int32_t M, char * S);
int32_t colour(int32_t ar, int32_t ac, int32_t br, int32_t bc);

#endif  // __RAINBOW_H
#endif
#line 7 "main.cpp"
#include <iostream>
#include <algorithm>
#include <utility>
#include <numeric>
#include <vector>
#include <array>
#include <cassert>
#include <set>
#include <map>

#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/chmin_chmax.cpp"

template <class T, class U>
constexpr bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

template <class T, class U>
constexpr bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) { 
    lhs = rhs; 
    return true; 
  }
  return false;
}

/**
 * @title Chmin/Chmax
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/range.cpp"

class range {
public:
  class iterator {
  private:
    int64_t M_position;

  public:
    constexpr iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { ++M_position; }
    constexpr bool operator != (iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };

  class reverse_iterator {
  private:
    int64_t M_position;
  
  public:
    constexpr reverse_iterator(int64_t position) noexcept: M_position(position) { }
    constexpr void operator ++ () noexcept { --M_position; }
    constexpr bool operator != (reverse_iterator other) const noexcept { return M_position != other.M_position; }
    constexpr int64_t operator * () const noexcept { return M_position; }

  };
  
private:
  const iterator M_first, M_last;

public:
  constexpr range(int64_t first, int64_t last) noexcept: M_first(first), M_last(std::max(first, last)) { }
  constexpr iterator begin() const noexcept { return M_first; }
  constexpr iterator end() const noexcept { return M_last; }
  constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator(*M_last - 1); } 
  constexpr reverse_iterator rend() const noexcept { return reverse_iterator(*M_first - 1); } 

};

/**
 * @title Range
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

#include <type_traits>
#include <iterator>
#line 6 "/Users/kodamankod/Desktop/Programming/Library/other/rev.cpp"

template <class T>
class rev_impl {
public:
  using iterator = typename std::decay<T>::type::reverse_iterator;

private:
  const iterator M_begin;
  const iterator M_end;

public:
  constexpr rev_impl(T &&cont) noexcept: M_begin(std::rbegin(cont)), M_end(std::rend(cont)) { }
  constexpr iterator begin() const noexcept { return M_begin; }
  constexpr iterator end() const noexcept { return M_end; }

};

template <class T>
constexpr decltype(auto) rev(T &&cont) {
  return rev_impl<T>(std::forward<T>(cont));
}

/**
 * @title Reverser
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

#line 4 "/Users/kodamankod/Desktop/Programming/Library/other/fix_point.cpp"

template <class Func>
struct fix_point_impl: private Func {
  explicit constexpr fix_point_impl(Func &&func): Func(std::forward<Func>(func)) { }
  template <class... Args>
  constexpr decltype(auto) operator () (Args &&... args) const {
    return Func::operator()(*this, std::forward<Args>(args)...);
  }
};

template <class Func>
constexpr decltype(auto) fix_point(Func &&func) {
  return fix_point_impl<Func>(std::forward<Func>(func));
}

/**
 * @title Lambda Recursion
 */
#line 2 "/Users/kodamankod/Desktop/Programming/Library/container/wavelet_matrix.cpp"

#line 2 "/Users/kodamankod/Desktop/Programming/Library/container/bit_vector.cpp"

#include <cstddef>
#include <cstdint>
#line 7 "/Users/kodamankod/Desktop/Programming/Library/container/bit_vector.cpp"

class bit_vector {
public:
  using size_type = size_t;
  using bit_type = uint64_t;
  using count_type = uint32_t;

private:
  static constexpr size_type S_block_size = 64;

  size_type M_size;
  std::vector<bit_type> M_block;
  std::vector<count_type> M_accum;

public:
  bit_vector() = default;
  template <class InputIterator>
  explicit bit_vector(InputIterator first, InputIterator last) { construct(first, last); }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) { 
    M_size = std::distance(first, last);
    size_type fixed_size = M_size / S_block_size + 1;
    M_block.assign(fixed_size, 0);
    M_accum.assign(fixed_size, 0);
    for (size_type i = 0; i < M_size; ++i) {
      M_block[i / S_block_size] |= (bit_type(*first) & 1) << (i & (S_block_size - 1));
      ++first;
    }
    for (size_type i = 1; i < fixed_size; ++i) {
      M_accum[i] = M_accum[i - 1] + __builtin_popcountll(M_block[i - 1]);
    }
  }

  bool access(size_type idx) const {
    return M_block[idx / S_block_size] >> (idx & (S_block_size - 1)) & 1;
  }
  size_type rank(bool value, size_type idx) const {
    bit_type mask = (bit_type(1) << (idx & (S_block_size - 1))) - 1;
    size_type res = M_accum[idx / S_block_size] + __builtin_popcountll(M_block[idx / S_block_size] & mask);
    return value ? res : idx - res;
  }
  size_type select(bool value, size_type idx) const {
    if (idx >= rank(value, M_size)) {
      return M_size;
    }
    size_type ok = 0, ng = M_size;
    while (ng - ok > 1) {
      size_type md = (ok + ng) >> 1;
      (rank(value, md) <= idx ? ok : ng) = md;
    }
    return ok;
  }
  size_type select(bool value, size_type idx, size_type l) const {
    return select(value, idx + rank(value, l));
  }

};

/**
 * @title Succinct Bit Vector
 */
#line 6 "/Users/kodamankod/Desktop/Programming/Library/container/wavelet_matrix.cpp"

template <class T, size_t W>
class wavelet_matrix {
public:
  using value_type = T;
  using size_type = size_t;

  static constexpr size_type word_size = W;

private:
  size_type M_size;
  std::array<bit_vector, word_size> M_fid;
  std::array<size_type, word_size> M_zero;

public:
  wavelet_matrix() = default;
  template <class InputIterator>
  explicit wavelet_matrix(InputIterator first, InputIterator last) { construct(first, last); }

  template <class InputIterator>
  void construct(InputIterator first, InputIterator last) { 
    M_size = std::distance(first, last);
    std::vector<bool> bit(M_size);
    std::vector<value_type> current(first, last);
    std::vector<value_type> next(M_size);
    for (size_type k = word_size; k--;) {
      auto l = next.begin(), r = next.rbegin();
      for (size_type i = 0; i < M_size; ++i) {
        bit[i] = current[i] >> k & 1;
        (bit[i] ? *(r++) : *(l++)) = current[i];
      }
      M_fid[k].construct(bit.begin(), bit.end());
      M_zero[k] = l - next.begin();
      std::reverse(next.rbegin(), r);
      current.swap(next);
    }
  }

  size_type rank(value_type value, size_type l, size_type r) const {
    for (size_type k = word_size; k--;) {
      bool p = value >> k & 1;
      l = M_fid[k].rank(p, l) + p * M_zero[k];
      r = M_fid[k].rank(p, r) + p * M_zero[k];
    }
    return r - l;
  }

  size_type select(value_type value, size_type index) const {
    std::array<size_type, word_size + 1> l, r;
    l[word_size] = 0;
    r[word_size] = M_size;
    for (size_type k = word_size; k--;) {
      bool p = value >> k & 1;
      l[k] = M_fid[k].rank(p, l[k + 1]) + p * M_zero[k];
      r[k] = M_fid[k].rank(p, r[k + 1]) + p * M_zero[k];
    }
    if (r[0] - l[0] <= index) {
      return M_size;
    }
    for (size_type k = 0; k < word_size; ++k) {
      bool p = value >> k & 1;
      index = M_fid[k].select(p, index, l[k + 1]) - l[k + 1];
    }
    return index;
  }

  value_type access(size_type index) const {
    value_type res = 0;
    for (size_type k = word_size; k--;) {
      bool p = M_fid[k].access(index);
      res |= value_type(p) << k;
      index = M_fid[k].rank(p, index) + p * M_zero[k];
    }
    return res;
  }

  value_type quantile(size_type index, size_type l, size_type r) const {
    value_type res = 0;
    for (size_type k = word_size; k--;) {
      size_type lc = M_fid[k].rank(1, l);
      size_type rc = M_fid[k].rank(1, r);
      size_type zc = (r - l) - (rc - lc);
      bool p = (index >= zc);
      res |= value_type(p) << k;
      if (p) {
        l = lc + M_zero[k];
        r = rc + M_zero[k];
        index -= zc;
      }
      else {
        l -= lc;
        r -= rc;
      }
    }
    return res;
  }

  size_type count(size_type l, size_type r, value_type value) const {
    size_type res = 0;
    for (size_type k = word_size; k--;) {
      size_type lc = M_fid[k].rank(1, l);
      size_type rc = M_fid[k].rank(1, r);
      if (value >> (k) & 1) {
        l = lc + M_zero[k];
        r = rc + M_zero[k];
      }
      else {
        l -= lc;
        r -= rc;
        res += (rc - lc);
      }
    }
    return res + (r - l);
  }
  size_type count(size_type l, size_type r, value_type lb, value_type ub) const {
    return count(l, r, lb) - count(l, r, ub);
  }

};

/**
 * @title Wavelet Matrix
 */
#line 22 "main.cpp"

using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;

constexpr i32 inf32 = (i32(1) << 30) - 1;
constexpr i64 inf64 = (i64(1) << 62) - 1;

constexpr i32 dx[] = { 0, 1, 0, -1, 1, 1, -1, -1 };
constexpr i32 dy[] = { 1, 0, -1, 0, 1, -1, 1, -1 };

struct count_points {
  wavelet_matrix<i32, 20> matrix;
  std::set<std::pair<i32, i32>> points;
  std::vector<i32> X;
  void add_point(i32 x, i32 y) {
    points.emplace(x, y);
  }
  void build() {
    std::vector<i32> Y;
    for (auto [x, y]: points) {
      X.push_back(x);
      Y.push_back(y);
    }
    matrix.construct(Y.begin(), Y.end());
  }
  i32 count(i32 l, i32 r, i32 lb, i32 ub) {
    if (l >= r || lb >= ub) return 0;
    i32 il = std::lower_bound(X.begin(), X.end(), l) - X.begin();
    i32 ir = std::lower_bound(X.begin(), X.end(), r) - X.begin();
    return matrix.count(il, ir, lb, ub);
  }
};

i32 H, W;
i32 query_counter;
count_points nov, noe_h, noe_w, noc;
std::set<std::pair<i32, i32>> river;

void disable(i32 x, i32 y) {
  river.emplace(x, y);
  nov.add_point(x, y);
  noe_h.add_point(x, y);
  noe_h.add_point(x - 1, y);
  noe_w.add_point(x, y);
  noe_w.add_point(x, y - 1);
  noc.add_point(x, y);
  noc.add_point(x - 1, y);
  noc.add_point(x, y - 1);
  noc.add_point(x - 1, y - 1);
}
 
bool adjacent(i32 x, i32 y) {
  if (river.find(std::make_pair(x, y)) != river.end()) {
    return false;
  }
  for (auto k: range(0, 8)) {
    if (river.find(std::make_pair(x + dx[k], y + dy[k])) != river.end()) {
      return true;
    }
  }
  return false;
}
 
void init(i32 R, i32 C, i32 sr, i32 sc, i32 M, char * S) {
  H = R, W = C;
  {
    i32 x = sr - 1, y = sc - 1;
    disable(x, y);
    for (auto i: range(0, M)) {
      char c = S[i];
      if (c == 'N') --x;
      if (c == 'E') ++y;
      if (c == 'W') --y;
      if (c == 'S') ++x;
      disable(x, y);
    }
  }
  nov.build();
  noe_h.build();
  noe_w.build();
  noc.build();
}
 
i32 colour(i32 ar, i32 ac, i32 br, i32 bc) {
  ++query_counter;
  --ar; --ac; --br; --bc;
  i64 V = (i64) (br - ar + 1) * (bc - ac + 1);
  i64 E = (i64) (br - ar) * (bc - ac + 1) + (i64) (bc - ac) * (br - ar + 1);
  i64 C = (i64) (br - ar) * (bc - ac);
  i32 tmp = nov.count(ar, br + 1, ac, bc + 1);
  if (tmp == 0) {
    return 1;
  }
  i32 tmp2 = nov.count(ar + 1, br, ac + 1, bc);
  if (tmp2 == tmp) {
    return ++C;
  }
  V -= nov.count(ar, br + 1, ac, bc + 1);
  E -= noe_h.count(ar, br, ac, bc + 1);
  E -= noe_w.count(ar, br + 1, ac, bc);
  C -= noc.count(ar, br, ac, bc);
  return C - E + V;
}

#ifdef LOCAL

#include <stdio.h>

static int R, C, M, Q;
static int sr, sc;
static char S[100000 + 5];

int main() {
    scanf("%d %d %d %d", &R, &C, &M, &Q);
    scanf("%d %d", &sr, &sc);
    if (M > 0) {
        scanf(" %s ", S);
    }

    init(R, C, sr, sc, M, S);

    int query;
    for (query = 0; query < Q; query++) {
        int ar, ac, br, bc;
        scanf("%d %d %d %d", &ar, &ac, &br, &bc);
        printf("%d\n", colour(ar, ac, br, bc));
    }

    return 0;
}

#endif

• Subtask 1: 0 / 11
• Subtask 2: 12 / 12
• Subtask 3: 0 / 24
• Subtask 4: 0 / 27
• Subtask 5: 0 / 26