結果
問題 | No.1668 Grayscale |
ユーザー | KoD |
提出日時 | 2021-09-03 22:19:37 |
言語 | C++23(draft) (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 772 ms / 4,000 ms |
コード長 | 3,375 bytes |
コンパイル時間 | 4,922 ms |
コンパイル使用メモリ | 251,568 KB |
実行使用メモリ | 76,408 KB |
最終ジャッジ日時 | 2023-08-21 22:29:33 |
合計ジャッジ時間 | 6,459 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,384 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,380 KB |
testcase_06 | AC | 245 ms
73,464 KB |
testcase_07 | AC | 246 ms
73,408 KB |
testcase_08 | AC | 60 ms
10,972 KB |
testcase_09 | AC | 772 ms
76,408 KB |
testcase_10 | AC | 199 ms
37,952 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 25 ms
7,556 KB |
testcase_14 | AC | 99 ms
16,524 KB |
testcase_15 | AC | 46 ms
9,988 KB |
testcase_16 | AC | 29 ms
7,748 KB |
testcase_17 | AC | 16 ms
5,908 KB |
testcase_18 | AC | 1 ms
4,384 KB |
testcase_19 | AC | 2 ms
4,384 KB |
testcase_20 | AC | 2 ms
4,380 KB |
testcase_21 | AC | 2 ms
4,376 KB |
testcase_22 | AC | 2 ms
4,380 KB |
testcase_23 | AC | 1 ms
4,380 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; constexpr u64 ceil_log2(const u64 x) { u64 e = 0; while (((u64)1 << e) < x) ++e; return e; } template <class T> class FenwickTree { usize logn; std::vector<T> data; public: explicit FenwickTree(const usize size = 0) { logn = ceil_log2(size + 1) - 1; data = std::vector<T>(size + 1, T(0)); } usize size() const { return data.size() - 1; } void add(usize i, const T& x) { assert(i < size()); i += 1; while (i < data.size()) { data[i] += x; i += i & -i; } } void subtract(usize i, const T& x) { assert(i < size()); i += 1; while (i < data.size()) { data[i] -= x; i += i & -i; } } T fold(usize l, usize r) const { assert(l <= r and r <= size()); T ret(0); while (l < r) { ret += data[r]; r -= r & -r; } while (r < l) { ret -= data[l]; l -= l & -l; } return ret; } template <class F> usize max_right(const F& f) const { assert(f(T(0))); usize i = 0; T sum(0); for (usize k = (1 << logn); k > 0; k >>= 1) { if (i + k <= size() && f(sum + data[i + k])) { i += k; sum += data[i]; } } return i; } }; template <class T> using Vec = std::vector<T>; void main_() { usize H, W, N; std::cin >> H >> W >> N; Vec<Vec<usize>> grid(H, Vec<usize>(W)); for (auto& v : grid) { for (auto& x : v) { std::cin >> x; x -= 1; } } Vec<Vec<usize>> list(N); const auto add = [&](const usize x, const usize y) { if (x != y) { list[std::max(x, y)].push_back(std::min(x, y)); } }; for (const auto i : rep(0, H)) { for (const auto j : rep(1, W)) { add(grid[i][j - 1], grid[i][j]); } } for (const auto i : rep(1, H)) { for (const auto j : rep(0, W)) { add(grid[i - 1][j], grid[i][j]); } } FenwickTree<usize> fen(N - 1); for (const auto r : rep(0, N)) { for (const auto l : list[r]) { if (fen.fold(l, r) == 0) { fen.add(r - 1, 1); } } } std::cout << fen.fold(0, N - 1) + 1 << '\n'; } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); main_(); return 0; }