結果

問題 No.1074 増殖
ユーザー ngtkanangtkana
提出日時 2020-06-05 23:22:16
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 42 ms / 2,000 ms
コード長 3,397 bytes
コンパイル時間 2,452 ms
コンパイル使用メモリ 212,628 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-22 17:53:29
合計ジャッジ時間 3,596 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 26 ms
4,376 KB
testcase_07 AC 26 ms
4,380 KB
testcase_08 AC 26 ms
4,380 KB
testcase_09 AC 32 ms
4,376 KB
testcase_10 AC 30 ms
4,380 KB
testcase_11 AC 21 ms
4,376 KB
testcase_12 AC 22 ms
4,380 KB
testcase_13 AC 42 ms
4,376 KB
testcase_14 AC 42 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#define ENABLE_DEBUG 0
// Kana's kitchen {{{
#include<bits/stdc++.h>
#define ALL(v) std::begin(v),std::end(v)
#define LOOP(k) for(i64 ngtkana_is_a_genius=0; ngtkana_is_a_genius<(i64)k; ngtkana_is_a_genius++)

using i32 = std::int_least32_t;
using i64 = std::int_least64_t;
using u32 = std::uint_least32_t;
using u64 = std::uint_least64_t;
using usize = std::size_t;

template <class T, class U> using pair = std::pair<U, T>;
template <class T> using diag_pair = std::pair<T, T>;
template <class... Args> using tuple = std::tuple<Args...>;
template <class T> using vec = std::vector<T>;
template <class T> using numr = std::numeric_limits<T>;

#ifdef NGTKANA
#include<debug.hpp>
#else
#define DEBUG(...)(void)0
#endif
/*}}}*/

i64 inf = 40'000;

struct stairs {
    std::map<i64, i64, std::greater<>> map;

    stairs()
        : map({{0, inf}, {inf, 0}}) {}

    i64 add(i64 x, i64 y) {
        DEBUG(map, x, y);
        auto lb = map.lower_bound(x);
        assert(lb!=map.begin() && lb!=map.end());
        if (y < std::prev(lb)->second) return 0;
        DEBUG(x, y, *lb);

        i64 ans = 0;
        while (true) {
            auto [x0, y0] = *std::prev(lb);
            auto [x1, y1] = *lb;
            assert(x1 <= x && x < x0);
            assert(y0 < y1 && y0 <= y);

            DEBUG(*lb, *std::prev(lb), (x - x1) * (y - y0));

            if (y < y1) {
                ans += (x - x1) * (y - y0);
                if (x1 < x && y0 < y) {
                    map.emplace(x, y);
                }
                DEBUG(ans, map);
                return ans;
            }

            assert(lb!=map.end());
            auto [x2, y2] = *std::next(lb);
            ans -= (x1 - x2) * (y1 - y0);
            lb = map.erase(lb);
        }
    }
};

template <usize N, class T, class... Args, std::enable_if_t<N==0, int> = 0>
auto mkvec(Args... args) {
    return T(args...);
}
template <usize N, class T, class... Args, std::enable_if_t<N!=0, int> = 0>
auto mkvec(usize sz, Args... args) {
    using value_type = std::decay_t<decltype(mkvec<N-1, T>(args...))>;
    return vec<value_type>(sz, value_type(args...));
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(15) << std::fixed;

    usize n;
    std::cin >> n;
    auto st = mkvec<2, stairs>(2, 2);
    while (n--) {
        vec<i64> x(2), y(2);
        std::cin >> x.at(0) >> y.at(0);
        std::cin >> x.at(1) >> y.at(1);
        x.at(0) = -x.at(0);
        y.at(0) = -y.at(0);

        i64 ans = 0;
        for (usize i=0; i<2; i++) {
            for (usize j=0 ;j<2; j++) {
                ans += st.at(i).at(j).add(x.at(i), y.at(j));
            }
        }
        std::cout << ans << '\n';
    }
}

/*
 * 第一象限のみを考えましょう。
 * x 座標が単調増加、y 座標が単調減少だと思います。（実際には x の降順の map です。）
 *
 * (a, b) が入力されました。
 * x <= a なる最大の x を取ります。(lower_bound)
 * 初回だけは、埋没チェックです。一つ右の y 座標以下だった場合は、何もしません。
 *
 * さて、とりあえず (x - a) * (y - b) を足しましょう。
 * b <= y ならば、自分が消えればみんな幸せになるので、それで † 終わり † にしましょう。
 * y < b ならば、(x, y) を消して、次を見ましょう。
 */
0