結果

問題 No.960 マンハッタン距離3
ユーザー PachicobuePachicobue
提出日時 2019-12-23 17:32:14
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,436 ms / 2,000 ms
コード長 4,004 bytes
コンパイル時間 2,754 ms
コンパイル使用メモリ 221,064 KB
実行使用メモリ 10,992 KB
最終ジャッジ日時 2023-10-17 18:39:43
合計ジャッジ時間 29,550 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 AC 2 ms
4,348 KB
testcase_03 AC 2 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 AC 2 ms
4,348 KB
testcase_06 AC 2 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 2 ms
4,348 KB
testcase_12 AC 2 ms
4,348 KB
testcase_13 AC 2 ms
4,348 KB
testcase_14 AC 2 ms
4,348 KB
testcase_15 AC 2 ms
4,348 KB
testcase_16 AC 2 ms
4,348 KB
testcase_17 AC 2 ms
4,348 KB
testcase_18 AC 1 ms
4,348 KB
testcase_19 AC 2 ms
4,348 KB
testcase_20 AC 2 ms
4,348 KB
testcase_21 AC 2 ms
4,348 KB
testcase_22 AC 2 ms
4,348 KB
testcase_23 AC 2 ms
4,348 KB
testcase_24 AC 2 ms
4,348 KB
testcase_25 AC 2 ms
4,348 KB
testcase_26 AC 2 ms
4,348 KB
testcase_27 AC 2 ms
4,348 KB
testcase_28 AC 2 ms
4,348 KB
testcase_29 AC 2 ms
4,348 KB
testcase_30 AC 2 ms
4,348 KB
testcase_31 AC 2 ms
4,348 KB
testcase_32 AC 2 ms
4,348 KB
testcase_33 AC 2 ms
4,348 KB
testcase_34 AC 2 ms
4,348 KB
testcase_35 AC 2 ms
4,348 KB
testcase_36 AC 2 ms
4,348 KB
testcase_37 AC 2 ms
4,348 KB
testcase_38 AC 2 ms
4,348 KB
testcase_39 AC 2 ms
4,348 KB
testcase_40 AC 2 ms
4,348 KB
testcase_41 AC 2 ms
4,348 KB
testcase_42 AC 2 ms
4,348 KB
testcase_43 AC 2 ms
4,348 KB
testcase_44 AC 2 ms
4,348 KB
testcase_45 AC 2 ms
4,348 KB
testcase_46 AC 2 ms
4,348 KB
testcase_47 AC 2 ms
4,348 KB
testcase_48 AC 2 ms
4,348 KB
testcase_49 AC 3 ms
4,348 KB
testcase_50 AC 3 ms
4,348 KB
testcase_51 AC 2 ms
4,348 KB
testcase_52 AC 2 ms
4,348 KB
testcase_53 AC 2 ms
4,348 KB
testcase_54 AC 2 ms
4,348 KB
testcase_55 AC 2 ms
4,348 KB
testcase_56 AC 2 ms
4,348 KB
testcase_57 AC 2 ms
4,348 KB
testcase_58 AC 2 ms
4,348 KB
testcase_59 AC 2 ms
4,348 KB
testcase_60 AC 2 ms
4,348 KB
testcase_61 AC 2 ms
4,348 KB
testcase_62 AC 2 ms
4,348 KB
testcase_63 AC 2 ms
4,348 KB
testcase_64 AC 2 ms
4,348 KB
testcase_65 AC 2 ms
4,348 KB
testcase_66 AC 2 ms
4,348 KB
testcase_67 AC 2 ms
4,348 KB
testcase_68 AC 2 ms
4,348 KB
testcase_69 AC 2 ms
4,348 KB
testcase_70 AC 2 ms
4,348 KB
testcase_71 AC 2 ms
4,348 KB
testcase_72 AC 2 ms
4,348 KB
testcase_73 AC 2 ms
4,348 KB
testcase_74 AC 2 ms
4,348 KB
testcase_75 AC 2 ms
4,348 KB
testcase_76 AC 2 ms
4,348 KB
testcase_77 AC 2 ms
4,348 KB
testcase_78 AC 2 ms
4,348 KB
testcase_79 AC 2 ms
4,348 KB
testcase_80 AC 2 ms
4,348 KB
testcase_81 AC 2 ms
4,348 KB
testcase_82 AC 1 ms
4,348 KB
testcase_83 AC 2 ms
4,348 KB
testcase_84 AC 2 ms
4,348 KB
testcase_85 AC 2 ms
4,348 KB
testcase_86 AC 2 ms
4,348 KB
testcase_87 AC 2 ms
4,348 KB
testcase_88 AC 2 ms
4,348 KB
testcase_89 AC 2 ms
4,348 KB
testcase_90 AC 2 ms
4,348 KB
testcase_91 AC 2 ms
4,348 KB
testcase_92 AC 2 ms
4,348 KB
testcase_93 AC 2 ms
4,348 KB
testcase_94 AC 2 ms
4,348 KB
testcase_95 AC 2 ms
4,348 KB
testcase_96 AC 2 ms
4,348 KB
testcase_97 AC 2 ms
4,348 KB
testcase_98 AC 2 ms
4,348 KB
testcase_99 AC 2 ms
4,348 KB
testcase_100 AC 2 ms
4,348 KB
testcase_101 AC 2 ms
4,348 KB
testcase_102 AC 2 ms
4,348 KB
testcase_103 AC 2 ms
4,348 KB
testcase_104 AC 2 ms
4,348 KB
testcase_105 AC 2 ms
4,348 KB
testcase_106 AC 2 ms
4,348 KB
testcase_107 AC 2 ms
4,348 KB
testcase_108 AC 2 ms
4,348 KB
testcase_109 AC 2 ms
4,348 KB
testcase_110 AC 2 ms
4,348 KB
testcase_111 AC 2 ms
4,348 KB
testcase_112 AC 2 ms
4,348 KB
testcase_113 AC 2 ms
4,348 KB
testcase_114 AC 2 ms
4,348 KB
testcase_115 AC 2 ms
4,348 KB
testcase_116 AC 2 ms
4,348 KB
testcase_117 AC 2 ms
4,348 KB
testcase_118 AC 2 ms
4,348 KB
testcase_119 AC 2 ms
4,348 KB
testcase_120 AC 2 ms
4,348 KB
testcase_121 AC 2 ms
4,348 KB
testcase_122 AC 2 ms
4,348 KB
testcase_123 AC 2 ms
4,348 KB
testcase_124 AC 2 ms
4,348 KB
testcase_125 AC 2 ms
4,348 KB
testcase_126 AC 2 ms
4,348 KB
testcase_127 AC 2 ms
4,348 KB
testcase_128 AC 23 ms
4,348 KB
testcase_129 AC 60 ms
5,712 KB
testcase_130 AC 43 ms
4,920 KB
testcase_131 AC 73 ms
6,240 KB
testcase_132 AC 734 ms
10,200 KB
testcase_133 AC 7 ms
4,348 KB
testcase_134 AC 21 ms
4,348 KB
testcase_135 AC 141 ms
5,712 KB
testcase_136 AC 152 ms
5,476 KB
testcase_137 AC 39 ms
4,348 KB
testcase_138 AC 361 ms
8,088 KB
testcase_139 AC 464 ms
8,880 KB
testcase_140 AC 79 ms
4,920 KB
testcase_141 AC 845 ms
10,464 KB
testcase_142 AC 224 ms
6,504 KB
testcase_143 AC 49 ms
4,392 KB
testcase_144 AC 1,043 ms
9,672 KB
testcase_145 AC 64 ms
4,348 KB
testcase_146 AC 134 ms
4,656 KB
testcase_147 AC 651 ms
7,824 KB
testcase_148 AC 46 ms
5,712 KB
testcase_149 AC 75 ms
6,504 KB
testcase_150 AC 114 ms
8,352 KB
testcase_151 AC 6 ms
4,348 KB
testcase_152 AC 55 ms
4,392 KB
testcase_153 AC 83 ms
4,920 KB
testcase_154 AC 16 ms
4,348 KB
testcase_155 AC 560 ms
7,824 KB
testcase_156 AC 224 ms
4,728 KB
testcase_157 AC 653 ms
7,824 KB
testcase_158 AC 508 ms
10,728 KB
testcase_159 AC 65 ms
4,636 KB
testcase_160 AC 20 ms
4,348 KB
testcase_161 AC 891 ms
8,352 KB
testcase_162 AC 70 ms
4,656 KB
testcase_163 AC 40 ms
4,348 KB
testcase_164 AC 120 ms
8,616 KB
testcase_165 AC 77 ms
6,504 KB
testcase_166 AC 14 ms
4,348 KB
testcase_167 AC 57 ms
6,240 KB
testcase_168 AC 226 ms
4,920 KB
testcase_169 AC 310 ms
5,184 KB
testcase_170 AC 263 ms
4,700 KB
testcase_171 AC 425 ms
5,976 KB
testcase_172 AC 35 ms
4,656 KB
testcase_173 AC 10 ms
4,348 KB
testcase_174 AC 130 ms
9,672 KB
testcase_175 AC 168 ms
10,992 KB
testcase_176 AC 90 ms
7,032 KB
testcase_177 AC 12 ms
4,348 KB
testcase_178 AC 113 ms
7,296 KB
testcase_179 AC 120 ms
9,144 KB
testcase_180 AC 73 ms
4,656 KB
testcase_181 AC 17 ms
4,348 KB
testcase_182 AC 32 ms
4,348 KB
testcase_183 AC 44 ms
4,348 KB
testcase_184 AC 34 ms
4,348 KB
testcase_185 AC 53 ms
4,392 KB
testcase_186 AC 65 ms
4,656 KB
testcase_187 AC 49 ms
4,392 KB
testcase_188 AC 2 ms
4,348 KB
testcase_189 AC 2 ms
4,348 KB
testcase_190 AC 2 ms
4,348 KB
testcase_191 AC 2 ms
4,348 KB
testcase_192 AC 2 ms
4,348 KB
testcase_193 AC 2 ms
4,348 KB
testcase_194 AC 2 ms
4,348 KB
testcase_195 AC 2 ms
4,348 KB
testcase_196 AC 507 ms
8,088 KB
testcase_197 AC 110 ms
4,936 KB
testcase_198 AC 403 ms
6,768 KB
testcase_199 AC 1,436 ms
8,616 KB
testcase_200 AC 64 ms
4,656 KB
testcase_201 AC 38 ms
4,348 KB
testcase_202 AC 248 ms
7,824 KB
testcase_203 AC 320 ms
6,504 KB
testcase_204 AC 861 ms
10,728 KB
testcase_205 AC 234 ms
6,240 KB
testcase_206 AC 72 ms
4,656 KB
testcase_207 AC 53 ms
4,392 KB
testcase_208 AC 682 ms
8,616 KB
testcase_209 AC 216 ms
4,920 KB
testcase_210 AC 48 ms
4,360 KB
testcase_211 AC 224 ms
5,712 KB
testcase_212 AC 18 ms
4,348 KB
testcase_213 AC 38 ms
4,348 KB
testcase_214 AC 639 ms
10,992 KB
testcase_215 AC 978 ms
9,408 KB
testcase_216 AC 1,079 ms
10,464 KB
testcase_217 AC 448 ms
7,296 KB
testcase_218 AC 76 ms
4,920 KB
testcase_219 AC 39 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using ll = long long;
int main()
{
    using pll = std::pair<ll, ll>;
    ll W, H;
    std::cin >> W >> H;
    auto enc   = [&](ll x, ll y) -> pll { return pll{x + y, y - x}; };
    auto dec   = [&](ll x, ll y) -> pll { return std::abs(x + y) % 2 == 1 ? pll{-1, -1} : pll{(x - y) / 2, (x + y) / 2}; };
    auto L1    = [&](ll x1, ll y1, ll x2, ll y2) { return std::abs(x1 - x2) + std::abs(y1 - y2); };
    auto is_in = [&](ll x, ll y) { return 1 <= y and y <= H and 1 <= x and x <= W; };
    int N;
    std::cin >> N;
    std::vector<ll> rxs(N), rys(N);
    for (int i = 0; i < N; i++) { std::cin >> rxs[i] >> rys[i]; }
    {
        std::set<ll> parity;
        for (int i = 0; i < N; i++) { parity.insert(std::abs(rxs[i] + rys[i]) % 2); }
        if (parity.size() == 2) { return std::cout << 0 << std::endl, 0; }
    }
    std::vector<ll> xs(N), ys(N);
    for (int i = 0; i < N; i++) { std::tie(xs[i], ys[i]) = enc(rxs[i], rys[i]); }
    auto is_ok = [&](ll x, ll y) {
        if (not is_in(x, y)) { return false; }
        std::set<ll> ds;
        for (int i = 0; i < N; i++) { ds.insert(L1(rxs[i], rys[i], x, y)); }
        return ds.size() == 1;
    };
    const ll ym = *std::min_element(ys.begin(), ys.end());
    const ll xm = *std::min_element(xs.begin(), xs.end());
    const ll yM = *std::max_element(ys.begin(), ys.end());
    const ll xM = *std::max_element(xs.begin(), xs.end());
    ll ps[]     = {xm + (yM - ym) / 2, xM - (yM - ym) / 2, (xm + xM) / 2, (xm + xM) / 2};
    ll qs[]     = {(ym + yM) / 2, (ym + yM) / 2, yM - (xM - xm) / 2, ym + (xM - xm) / 2};
    for (int i = 0; i < 4; i++) { std::tie(ps[i], qs[i]) = dec(ps[i], qs[i]); }
    if (xm == xM) {
        if (not is_ok(ps[0], qs[0]) or not is_ok(ps[1], qs[1])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[0] + 1) * (H - qs[0] + 1) + ps[1] * qs[1];
        if (N == 2) { ans += (ps[0] - ps[1] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    if (ym == yM) {
        if (not is_ok(ps[2], qs[2]) or not is_ok(ps[3], qs[3])) { return std::cout << 0 << std::endl, 0; }
        ll ans = (W - ps[2] + 1) * qs[2] + ps[3] * (H - qs[3] + 1);
        if (N == 2) { ans += (ps[2] - ps[3] - 1); }
        return std::cout << ans << std::endl, 0;
    }
    std::set<pll> start;
    for (int i = 0; i < 4; i++) {
        if (is_ok(ps[i], qs[i])) { start.insert({ps[i], qs[i]}); }
    }
    ll ans = start.size();
    if (start.size() == 1) {
        const auto [p, q] = *start.begin();
        constexpr ll dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p + mid * dx[i], nq = q + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    } else if (start.size() == 2) {
        const auto [p0, q0] = *start.begin();
        const auto [p1, q1] = *start.rbegin();
        constexpr ll dx[]   = {-1, -1, -1, 0, 0, 1, 1, 1};
        constexpr ll dy[]   = {-1, 0, 1, -1, 1, -1, 0, 1};
        for (int i = 0; i < 8; i++) {
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p0 + mid * dx[i], nq = q0 + mid * dy[i];
                (is_ok(np, nq) and (np != p1 or nq != q1) ? inf : sup) = mid;
            }
            ans += inf;
        }
        for (int i = 0; i < 8; i++) {
            if (dx[i] != 0 and dy[i] != 0) { continue; }
            ll inf = 0, sup = H + W;
            while (sup - inf > 1) {
                const ll mid = (inf + sup) / 2;
                const ll np = p1 + mid * dx[i], nq = q1 + mid * dy[i];
                (is_ok(np, nq) ? inf : sup) = mid;
            }
            ans += inf;
        }
    }
    std::cout << ans << std::endl;
    return 0;
}
0