結果
| 問題 | No.1874 Minimum of Sum of Rectangles |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2022-03-11 20:55:45 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 850 ms / 3,000 ms |
| コード長 | 6,297 bytes |
| コンパイル時間 | 2,736 ms |
| コンパイル使用メモリ | 222,156 KB |
| 最終ジャッジ日時 | 2025-01-28 08:03:53 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 39 |
ソースコード
#include <bits/stdc++.h>using i64 = int64_t;std::vector<int> press(std::vector<int> &vec) {auto p = vec;std::sort(p.begin(), p.end());p.erase(std::unique(p.begin(), p.end()), p.end());for (auto &e : vec) e = (int)(std::lower_bound(p.begin(), p.end(), e) - p.begin());return p;}template <class M> struct SegmentTree {using T = typename M::Type;int n, size;std::vector<T> data;SegmentTree(int n_) : n(n_) {size = 1;while (size < n) size <<= 1;data.assign(2 * size, M::id());}void set(int i, const T val) {assert(0 <= i and i < n);i += size;data[i] = val;while (i != 1) {i >>= 1;data[i] = M::op(data[2 * i], data[2 * i + 1]);}}T get(int i) {assert(0 <= i and i < n);i += size;return data[i];}T fold(int l, int r) {assert(0 <= l and l <= r and r <= n);T pl = M::id(), pr = M::id();for (l += size, r += size; l < r; l >>= 1, r >>= 1) {if (l & 1) pl = M::op(pl, data[l++]);if (r & 1) pr = M::op(data[--r], pr);}return M::op(pl, pr);}T fold() { return data[1]; }template <class F> int calc_max_right(int l, const F &f) {assert(0 <= l and l <= n);assert(f(M::id()));if (l == n) return n;l += size;T product = M::id();do {while (l % 2 == 0) l >>= 1;if (not f(M::op(product, data[l]))) {while (l < size) {l <<= 1;if (f(M::op(product, data[l]))) product = M::op(product, data[l++]);}return l - size;}product = M::op(product, data[l++]);} while ((l & -l) != l);return n;}};struct M1 {struct Type {i64 u;i64 l;int cu;int cl;};static Type op(const Type a, const Type b) {return {a.u + b.u,a.l + b.l,a.cu + b.cu,a.cl + b.cl,};}static Type id() { return {0, 0, 0, 0}; }};struct M2 {struct Type {i64 a;i64 b;};static Type op(const Type a, const Type b) { return {a.a + b.a, a.b + b.b}; }static Type id() { return {0, 0}; }};struct M3 {using Type = i64;static Type op(const Type a, const Type b) { return a + b; }static Type id() { return 0; }};constexpr int max_xy = 1000000;int main() {int N;std::cin >> N;std::vector<int> X(N), Y(N);for (int i = 0; i < N; ++i) std::cin >> X[i] >> Y[i];auto get_list = [&]() {const auto x_p = press(X), y_p = press(Y);const int sx = (int)x_p.size(), sy = (int)y_p.size();SegmentTree<M1> seg(sy);for (int i = 0; i < N; ++i) {seg.set(Y[i], M1::op(seg.get(Y[i]), {0, x_p[X[i]], 0, 1}));}std::vector<std::vector<int>> events(sx);for (int i = 0; i < N; ++i) events[X[i]].push_back(i);auto calc_sum = [&](const M1::Type v, const int x) {return ((i64)v.cu * x_p[x] - v.u) + (v.l - (i64)v.cl * x_p[x]);};std::vector<std::pair<int, int>> points;points.reserve(sx);for (int x = 0; x < sx; ++x) {for (const int i : events[x]) {auto v = seg.get(Y[i]);v.l -= x_p[X[i]];--v.cl;v.u += x_p[X[i]];++v.cu;seg.set(Y[i], v);}const i64 all_sum = calc_sum(seg.fold(), x);auto f = [&](M1::Type v) {const i64 sum = calc_sum(v, x);return 2 * sum <= all_sum;};const int r = seg.calc_max_right(0, f);if (r != sy) points.push_back({x, r});if (r != 0) points.push_back({x, r - 1});}for (int i = 0; i < N; ++i) {X[i] = x_p[X[i]];Y[i] = y_p[Y[i]];}for (auto &[x, y] : points) {x = x_p[x];y = y_p[y];}return points;};auto points = get_list();const int M = (int)points.size();std::vector<i64> res(M);auto rotate = [&]() {auto conv = [&](int &x, int &y) {const int nx = max_xy - y;const int ny = x;x = nx;y = ny;};for (int i = 0; i < N; ++i) conv(X[i], Y[i]);for (auto &[x, y] : points) conv(x, y);};auto run = [&]() {const auto x_p = press(X), y_p = press(Y);const int sx = (int)x_p.size(), sy = (int)y_p.size();for (auto &[x, y] : points) {x = (int)(std::lower_bound(x_p.begin(), x_p.end(), x) - x_p.begin());y = (int)(std::lower_bound(y_p.begin(), y_p.end(), y) - y_p.begin());}SegmentTree<M2> seg_f(sy);SegmentTree<M3> seg_s(sy), seg_c(sy);std::vector<std::vector<int>> event_a(sx), event_q(sx);for (int i = 0; i < N; ++i) event_a[X[i]].push_back(i);for (int i = 0; i < M; ++i) event_q[points[i].first].push_back(i);for (int x = 0; x < sx; ++x) {for (const int i : event_a[x]) {const int y = Y[i];seg_f.set(y, M2::op(seg_f.get(y), {y_p[y], -((i64)y_p[y] * x_p[x])}));seg_s.set(y, seg_s.get(y) + x_p[x]);seg_c.set(y, seg_c.get(y) + 1);}for (const int i : event_q[x]) {const int y = points[i].second;i64 sum = (seg_c.fold(0, y) * x_p[x] - seg_s.fold(0, y)) * y_p[y];const auto f = seg_f.fold(0, y);sum -= x_p[x] * f.a + f.b;res[i] += sum;}}for (int i = 0; i < N; ++i) {X[i] = x_p[X[i]];Y[i] = y_p[Y[i]];}for (auto &[x, y] : points) {x = x_p[x];y = y_p[y];}};for ([[maybe_unused]] int i = 0; i < 4; ++i) {run();rotate();}std::cout << *std::min_element(res.begin(), res.end()) << std::endl;}