結果

問題 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0