#698973 (C++17) No.1679 マスゲーム

提出ソース
結果

問題	No.1679 マスゲーム
ユーザー	Cyanmond
提出日時	2021-09-11 18:32:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	90 ms / 2,000 ms
コード長	17,136 bytes
コンパイル時間	2,106 ms
コンパイル使用メモリ	207,924 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-06-23 02:48:10
合計ジャッジ時間	4,599 ms
ジャッジサーバーID （参考情報）	judge3 / judge1
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	3 ms 5,376 KB
testcase_02	AC	3 ms 5,376 KB
testcase_03	AC	86 ms 5,376 KB
testcase_04	AC	90 ms 5,376 KB
testcase_05	AC	86 ms 5,376 KB
testcase_06	AC	86 ms 5,376 KB
testcase_07	AC	83 ms 5,376 KB
testcase_08	AC	86 ms 5,376 KB
testcase_09	AC	87 ms 5,376 KB
testcase_10	AC	83 ms 5,376 KB
testcase_11	AC	80 ms 5,376 KB
testcase_12	AC	9 ms 5,376 KB
testcase_13	AC	33 ms 5,376 KB
testcase_14	AC	84 ms 5,376 KB
testcase_15	AC	71 ms 5,376 KB
testcase_16	AC	62 ms 5,376 KB
testcase_17	AC	2 ms 5,376 KB
testcase_18	AC	56 ms 5,376 KB
testcase_19	AC	2 ms 5,376 KB
testcase_20	AC	2 ms 5,376 KB
testcase_21	AC	2 ms 5,376 KB
testcase_22	AC	2 ms 5,376 KB
testcase_23	AC	2 ms 5,376 KB
testcase_24	AC	2 ms 5,376 KB
testcase_25	AC	2 ms 5,376 KB
testcase_26	AC	2 ms 5,376 KB
testcase_27	AC	3 ms 5,376 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include "bits/stdc++.h"

#pragma region temp

// utility
namespace cmitf {
using usize = std::size_t;
using isize = std::ptrdiff_t;
using bit_t = std::uint64_t;

constexpr std::int64_t operator""_i64(unsigned long long n) noexcept {
  return static_cast<std::int64_t>(n);
}
constexpr std::int32_t operator""_i32(unsigned long long n) noexcept {
  return static_cast<std::int32_t>(n);
}
constexpr std::int16_t operator""_i16(unsigned long long n) noexcept {
  return static_cast<std::int16_t>(n);
}

constexpr std::uint64_t operator""_u64(unsigned long long n) noexcept {
  return static_cast<std::uint64_t>(n);
}
constexpr std::uint32_t operator""_u32(unsigned long long n) noexcept {
  return static_cast<std::uint32_t>(n);
}
constexpr std::uint16_t operator""_u16(unsigned long long n) noexcept {
  return static_cast<std::uint16_t>(n);
}

constexpr usize operator""_uz(unsigned long long n) noexcept { return static_cast<usize>(n); }
constexpr isize operator""_iz(unsigned long long n) noexcept { return static_cast<isize>(n); }
constexpr bit_t operator""_bit(unsigned long long n) noexcept { return static_cast<bit_t>(n); }

template <class T, T Div = 2>
constexpr T infty = std::numeric_limits<T>::max() / Div - 10;
constexpr std::int32_t infi32 = infty<std::int32_t, 2>;  // 1073741813
constexpr std::int64_t infi64 = infty<std::int64_t, 4>;  // 2305843009213693941
constexpr usize infusz = infi32;

#if __cplusplus < 202002L
constexpr std::int32_t popcount(std::uint64_t x) noexcept {
  x = x - ((x >> 1) & 0x5555555555555555);
  x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;
  x = x + (x >> 8);
  x = x + (x >> 16);
  x = x + (x >> 32);
  return x & 0x0000007f;
}
#else
using std::popcount;
#endif

template <typename T>
constexpr T ceil_div(const T a, const T b) {
  return (a + b - 1) / b;
}

template <class T>
auto mk_vec(const usize n, const T& value) {
  return std::vector(n, value);
}
template <class... Args>
auto mk_vec(const usize n, Args... args) {
  return std::vector(n, mk_vec(args...));
}

namespace helper {
template <class T, class... Tail>
void zip_sort_renumber(const std::vector<usize>& order, std::vector<T>& head, Tail&... tail) {
  const usize n = order.size();
  std::vector<T> sorted_head(n);
  for (usize i = 0; i < n; ++i) sorted_head[i] = head[order[i]];
  head = std::move(sorted_head);
  if constexpr (sizeof...(Tail) != 0) zip_sort_renumber(order, tail...);
}
}  // namespace helper

template <class Head, class... Tail>
std::vector<usize> zip_sort(std::vector<Head>& head, std::vector<Tail>&... tail) {
  const usize n = head.size();

  std::vector<std::tuple<Head, Tail..., usize>> res(n);
  for (usize i = 0; i < n; ++i) res[i] = std::make_tuple(head[i], tail[i]..., i);
  std::sort(res.begin(), res.end());

  std::vector<usize> order(n);
  for (usize i = 0; i < n; ++i)
    order[i] = std::get<std::tuple_size_v<std::tuple<Head, Tail...>>>(res[i]);
  helper::zip_sort_renumber(order, head, tail...);
  return order;
}

template <class T>
class presser {
  using size_type = std::size_t;
  std::vector<T> m_v;

 public:
  size_type size() const noexcept { return m_v.size(); }

  void reserve(const size_type n) { m_v.reserve(n); }

  template <class ForwardIterator>
  void paste(const ForwardIterator first, const ForwardIterator last) {
    std::copy(first, last, std::back_inserter(m_v));
  }

  template <class Container>
  void paste(const Container& c) {
    std::copy(c.begin(), c.end(), std::back_inserter(m_v));
  }

  void add(const T& v) { m_v.push_back(v); }

  size_type build() {
    std::sort(m_v.begin(), m_v.end());
    m_v.erase(std::unique(m_v.begin(), m_v.end()), m_v.end());
    return m_v.size();
  }

  size_type get_idx(const T& val) const {
    return static_cast<size_type>(std::lower_bound(m_v.begin(), m_v.end(), val) - m_v.begin());
  }

  T get_val(const size_type i) const { return m_v[i]; }
};

class rep {
  using value_type = usize;

  struct rep_iterator {
    value_type itr;
    constexpr rep_iterator(const value_type pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { ++itr; }
    constexpr bool operator!=(const rep_iterator& other) const noexcept { return itr != other.itr; }
    constexpr value_type operator*() const noexcept { return itr; }
  };
  const rep_iterator first, last;

 public:
  constexpr rep(const value_type first_, const value_type last_) noexcept
      : first(first_), last(std::max(first_, last_)) {}
  constexpr rep_iterator begin() const noexcept { return first; }
  constexpr rep_iterator end() const noexcept { return last; }
};  // class rep

class revrep {
  using value_type = usize;
  struct revrep_iterator {
    value_type itr;
    constexpr revrep_iterator(const value_type pos) noexcept : itr(pos) {}
    constexpr void operator++() noexcept { --itr; }
    constexpr bool operator!=(const revrep_iterator& other) const noexcept {
      return itr != other.itr;
    }
    constexpr usize operator*() const noexcept { return itr; }
  };
  const revrep_iterator first, last;

 public:
  constexpr revrep(const usize first_, const usize last_) noexcept
      : first(last_ - 1), last(first_ - 1) {}
  constexpr revrep_iterator begin() const noexcept { return first; }
  constexpr revrep_iterator end() const noexcept { return last; }
};  // class revrep

template <class F>
class rec_lambda {
  F f;

 public:
  explicit constexpr rec_lambda(F&& f_) : f(std::forward<F>(f_)) {}
  template <class... Args>
  constexpr auto operator()(Args&&... args) const {
    return f(*this, std::forward<Args>(args)...);
  }
};  // class rec_lambda

class to4 {
  using value_type = usize;

  static constexpr value_type minus1 = std::numeric_limits<value_type>::max();
  static constexpr std::array<value_type, 5> dx = {minus1, 0, 1, 0, 0}, dy = {0, minus1, 0, 1, 0};

  struct to4_iterator {
    int d;
    const value_type h, w, maxh, maxw;
    constexpr to4_iterator(const value_type h_, const value_type w_, const value_type maxh_,
                           const value_type maxw_) noexcept
        : d(0), h(h_), w(w_), maxh(maxh_), maxw(maxw_) {}
    constexpr void operator++() noexcept {
      do {
        ++d;
      } while (d != 4 and (h + dx[d] == minus1 or h + dx[d] == maxh or w + dy[d] == minus1 or
                           w + dy[d] == maxw));
    }
    constexpr bool operator!=(const int other) const noexcept { return d != other; }
    constexpr std::pair<value_type, value_type> operator*() const noexcept {
      return {h + dx[d], w + dy[d]};
    }
  };

  const to4_iterator i;

 public:
  constexpr to4(const value_type h, const value_type w, const value_type maxh,
                const value_type maxw) noexcept
      : i(h, w, maxh, maxw) {}
  constexpr to4_iterator begin() const noexcept { return i; }
  constexpr int end() const noexcept { return 4; }
};

class to8 {
  using value_type = usize;

  static constexpr value_type minus1 = std::numeric_limits<value_type>::max();
  static constexpr std::array<value_type, 9> dx = {minus1, minus1, minus1, 0, 0, 1, 1, 1, 0},
                                             dy = {minus1, 0, 1, minus1, 1, minus1, 0, 1, 0};

  struct to8_iterator {
    int d;
    const value_type h, w, maxh, maxw;
    constexpr to8_iterator(const value_type h_, const value_type w_, const value_type maxh_,
                           const value_type maxw_) noexcept
        : d(0), h(h_), w(w_), maxh(maxh_), maxw(maxw_) {}
    constexpr void operator++() noexcept {
      do {
        ++d;
      } while (d != 8 and (h + dx[d] == minus1 or h + dx[d] == maxh or w + dy[d] == minus1 or
                           w + dy[d] == maxw));
    }
    constexpr bool operator!=(const int other) const noexcept { return d != other; }
    constexpr std::pair<value_type, value_type> operator*() const noexcept {
      return {h + dx[d], w + dy[d]};
    }
  };

  const to8_iterator i;

 public:
  constexpr to8(const value_type h, const value_type w, const value_type maxh,
                const value_type maxw) noexcept
      : i(h, w, maxh, maxw) {}
  constexpr to8_iterator begin() const noexcept { return i; }
  constexpr int end() const noexcept { return 8; }
};
}  // namespace cmitf

// math
namespace cmitf {
constexpr std::int64_t pow_int(std::int64_t x, std::int64_t n) noexcept {
  assert(n >= 0);
  std::int64_t res = 1;
  while (n != 0) {
    if (n & 1) res = res * x;
    x = x * x;
    n >>= 1;
  }
  // res = x ^ n
  return res;
}

constexpr std::uint32_t ceil_log2(std::uint64_t v) noexcept {
  std::uint32_t res = 0;
  while ((1_u64 << res) < v) ++res;
  return res;
}

template <std::uint32_t MOD>
class Static_Modint {
  using this_type = Static_Modint;
  std::uint32_t value;

 public:
  static constexpr std::uint32_t mod() noexcept { return MOD; }
  template <class T>
  static constexpr T mod() noexcept {
    return static_cast<T>(MOD);
  }

  template <class T, std::enable_if_t<std::is_unsigned_v<T>>* = nullptr>
  static constexpr std::uint32_t normalize(const T v) noexcept {
    return static_cast<std::uint32_t>(v % mod<T>());
  }
  template <class T, std::enable_if_t<std::is_signed_v<T>>* = nullptr>
  static constexpr std::uint32_t normalize(const T v) noexcept {
    if (v < 0)
      return static_cast<std::uint32_t>(v % mod<T>() + mod<T>());
    else
      return static_cast<std::uint32_t>(v % mod<T>());
  }

  constexpr Static_Modint() noexcept : value(0) {}
  template <class T>
  constexpr Static_Modint(const T v) noexcept : value(normalize(v)) {}

  template <class T>
  static constexpr this_type raw(const T v) noexcept {
    this_type ret;
    ret.value = static_cast<std::uint32_t>(v);
    return ret;
  }

  constexpr const std::uint32_t& val() const noexcept { return value; }
  constexpr this_type operator-() const noexcept { return value == 0 ? 0 : mod() - value; }

  constexpr bool operator==(const this_type& rhs) const noexcept { return value == rhs.value; }
  constexpr bool operator!=(const this_type& rhs) const noexcept { return value != rhs.value; }
  constexpr bool operator<(const this_type& rhs) const noexcept { return value < rhs.value; }
  constexpr bool operator<=(const this_type& rhs) const noexcept { return value <= rhs.value; }
  constexpr bool operator>(const this_type& rhs) const noexcept { return value > rhs.value; }
  constexpr bool operator>=(const this_type& rhs) const noexcept { return value >= rhs.value; }
  constexpr this_type& operator++() noexcept {
    ++value;
    if (value == mod()) value = 0;
    return *this;
  }
  constexpr this_type& operator--() noexcept {
    if (value == 0) value = mod();
    --value;
    return *this;
  }
  constexpr this_type operator++(int) noexcept {
    this_type ret(*this);
    ++*this;
    return ret;
  }
  constexpr this_type operator--(int) noexcept {
    this_type ret(*this);
    --*this;
    return ret;
  }

  constexpr this_type operator+(const this_type& rhs) const noexcept {
    return this_type(*this) += rhs;
  }
  constexpr this_type operator-(const this_type& rhs) const noexcept {
    return this_type(*this) -= rhs;
  }
  constexpr this_type operator*(const this_type& rhs) const noexcept {
    return this_type(*this) *= rhs;
  }
  constexpr this_type operator/(const this_type& rhs) const noexcept {
    return this_type(*this) /= rhs;
  }

  constexpr this_type& operator+=(const this_type& rhs) noexcept {
    if ((value += rhs.value) >= mod()) value -= mod();
    return *this;
  }
  constexpr this_type& operator-=(const this_type& rhs) noexcept {
    if (value < rhs.value) value += mod();
    value -= rhs.value;
    return *this;
  }
  constexpr this_type& operator*=(const this_type& rhs) noexcept {
    value =
        static_cast<std::uint32_t>(static_cast<std::uint64_t>(value) *
                                   static_cast<std::uint64_t>(rhs.value) % mod<std::uint64_t>());
    return *this;
  }
  constexpr this_type& operator/=(const this_type& rhs) noexcept { return *this *= rhs.inv(); }

  template <class T>
  constexpr this_type pow(T n) {
    this_type ret(1), x(*this);
    while (n != 0) {
      if (n & 1) ret *= x;
      x *= x;
      n >>= 1;
    }
    return ret;
  }
  constexpr this_type inv() const {
    std::int64_t s = mod<std::int64_t>(), t = static_cast<std::int64_t>(value), a = 0, b = 1;
    while (t != 0) {
      const std::int64_t u = s / t;
      s -= t * u;
      a -= b * u;
      auto k = s;
      s = t;
      t = k;
      k = a;
      a = b;
      b = k;
    }
    if (a < 0) a += mod<std::int64_t>();
    return this_type::raw(a);
  }
};

template <class T>
class Static_Modint_Utility {
  using size_type = size_t;
  static inline size_type size = 1;

 public:
  static void upsize(const size_type n) {
    if (n > size) {
      for (size_type i = size + 1; i <= n; ++i) {
        fact.emplace_back(fact[i - 1] * T::raw(i));
        inv.emplace_back(-inv[T::mod() % i] * (T::mod() / i));
        fact_inv.emplace_back(fact_inv[i - 1] * inv[i]);
      }
      size = n;
    }
  }

  static inline std::vector<T> fact = {1, 1}, inv = {0, 1}, fact_inv = {1, 1};

  static T comb(const size_type n, const size_type r) {
    if (n < r) return 0;
    upsize(n);
    return fact[n] * fact_inv[n - r] * fact_inv[r];
  }
};
}  // namespace cmitf

// io
namespace cmitf {
template <class T, class U>
std::istream& operator>>(std::istream& is, std::pair<T, U>& v) {
  is >> v.first >> v.second;
  return is;
}
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& v) {
  os << v.first << ' ' << v.second;
  return os;
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
  for (auto& t : v) is >> t;
  return is;
}
template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  usize n = v.size();
  os << v[0];
  for (usize i = 1; i < n; ++i) os << ' ' << v[i];
  return os;
}

template <std::uint32_t MOD>
std::ostream& operator<<(std::ostream& os, const Static_Modint<MOD>& v) {
  os << v.val();
  return os;
}

inline void in() noexcept {}
template <class Head, class... Tail>
inline void in(Head& h, Tail&... t) {
  std::cin >> h;
  in(t...);
}

inline void lout() { std::cout << '\n'; }
template <class Head, class... Tail>
inline void lout(const Head& h, const Tail&... t) {
  std::cout << h;
  if constexpr (sizeof...(Tail) != 0) std::cout << ' ';
  lout(t...);
}

inline void sout() {}
template <class Head, class... Tail>
inline void sout(const Head& h, const Tail&... t) {
  std::cout << h << ' ';
  sout(t...);
}
}  // namespace cmitf

#pragma endregion

namespace cmitf {
#pragma region

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using std::ignore;
using std::make_pair;
using std::make_tuple;
using std::nullopt;
using std::pair;
using std::tuple;

using Str = std::string;
template <class T>
using Vec = std::vector<T>;
template <class T, std::size_t N>
using Array = std::array<T, N>;
template <class T>
using Que = std::queue<T>;
template <class T>
using Stk = std::stack<T>;
template <class T>
using Deq = std::deque<T>;
template <class T>
using HeapQ = std::priority_queue<T>;
template <class T>
using Set = std::set<T>;
template <class T>
using MultiSet = std::multiset<T>;
template <class T, class U>
using Map = std::map<T, U>;
template <class T, class U>
using MultiMap = std::multimap<T, U>;
template <class T>
using RevHeapQ = std::priority_queue<T, Vec<T>, std::greater<T>>;
template <class T>
using Opt = std::optional<T>;

#ifdef CMITF_DEBUG
// output "Debug : names = values"
#define pdebug(...)                                   \
  {                                                   \
    std::cerr << "Debug : " << #__VA_ARGS__ << " = "; \
    debug_impl::converter(__VA_ARGS__);               \
  }
#else
#define pdebug(...)
#endif

#pragma endregion

void main_() {
  usize N;
  in(N);
  Vec<i64> F, G;
  for (const auto i : rep(0, N)) {
    int a;
    i64 b, t;
    in(a, b, t);
    if (a == 0)
      F.push_back(t - b);
    else
      G.push_back(t - b);
  }

  std::sort(F.begin(), F.end());
  i64 ans = 0;
  for (const auto v : G)
    ans += i64(std::upper_bound(F.begin(), F.end(), v) - (std::lower_bound(F.begin(), F.end(), v)));

  lout(ans);
}

#undef pdebug
}  // namespace cmitf

int main() {
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(nullptr);

  // freopen("input.txt", "r", stdin);

  std::size_t T = 1;
  // std::cin >> T;
  while (T--) cmitf::main_();
  return 0;
}
yukicoder

結果

テストケース

ソースコード
