結果

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

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) ::std::begin(x), ::std::end(x)
using namespace std;

struct subsolver {
    map<int64_t, int64_t> f;
    subsolver() {
        f[0] = INT64_MAX;
        f[INT64_MAX] = 0;
    }
    int64_t operator () (int64_t y, int64_t x) {
        auto it = f.lower_bound(x);
        int64_t last_y = it->second;
        if (y <= last_y) return 0;

        int64_t delta = 0;
        while (it != f.begin()) {
            -- it;
            delta += (x - it->first) * (min(y, it->second) - last_y);
            last_y = it->second;
            if (it->second <= y) {
                it = f.erase(it);
            }
            if (y <= it->second) {
                break;
            }
        }
        f[x] = y;
        return delta;
    }
};

vector<int64_t> solve(int n, const vector<int64_t> & left, const vector<int64_t> & bottom, const vector<int64_t> & right, const vector<int64_t> & top) {
    array<subsolver, 4> s = {};
    vector<int64_t> ans(n);
    REP (i, n) {
        ans[i] += s[0](top[i], right[i]);
        ans[i] += s[1](top[i], - left[i]);
        ans[i] += s[2](- bottom[i], right[i]);
        ans[i] += s[3](- bottom[i], - left[i]);
    }
    return ans;
}

// generated by online-judge-template-generator v4.1.1 (https://github.com/kmyk/online-judge-template-generator)
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    constexpr char endl = '\n';
    int N; cin >> N;
    vector<int64_t> Xa(N), Ya(N), Xb(N), Yb(N);
    REP (i, N) {
        cin >> Xa[i] >> Ya[i] >> Xb[i] >> Yb[i];
    }
    auto ans = solve(N, Xa, Ya, Xb, Yb);
    REP (i, N) {
        cout << ans[i] << endl;
    }
    return 0;
}
0