結果

問題 No.1074 増殖
コンテスト
ユーザー ngtkana
提出日時 2020-06-05 23:23:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 2,000 ms
コード長 3,225 bytes
コンパイル時間 3,281 ms
コンパイル使用メモリ 207,472 KB
最終ジャッジ日時 2025-01-10 23:00:17
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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) {
        auto lb = map.lower_bound(x);
        assert(lb!=map.begin() && lb!=map.end());
        if (y < std::prev(lb)->second) return 0;

        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);


            if (y < y1) {
                ans += (x - x1) * (y - y0);
                if (x1 < x && y0 < y) {
                    map.emplace(x, y);
                }
                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);
        for (usize i=0; i<2; i++) {
            std::cin >> x.at(i) >> y.at(i);
            if (i==0) x.at(i) *= -1, y.at(i) *= -1;
        }

        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