結果
| 問題 | No.1874 Minimum of Sum of Rectangles |
| ユーザー |
 Cyanmond
|
| 提出日時 | 2022-02-28 01:08:41 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 6,450 bytes |
| コンパイル時間 | 2,724 ms |
| コンパイル使用メモリ | 221,628 KB |
| 最終ジャッジ日時 | 2025-01-28 03:51:47 |
|
ジャッジサーバーID （参考情報） |
judge4 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 RE * 1 |
| other | AC * 14 RE * 25 |
ソースコード
#include <bits/stdc++.h>using i64 = int64_t;constexpr i64 inf64 = 1500000000000000000;template <typename T> void setmin(T &v, const T a) {if (v > a) v = a;}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();std::vector<std::pair<int, int>> points;SegmentTree<M1> seg(sx);for (int i = 0; i < N; ++i)seg.set(X[i], M1::op(seg.get(X[i]), {0, y_p[Y[i]], 0, 1}));std::vector<std::vector<int>> events(sx);for (int i = 0; i < N; ++i) events[Y[i]].push_back(i);auto calc_sum = [&](const M1::Type v, const int y) {return (v.cu * y_p[y] - v.u) + (v.l - v.cl * y_p[y]);};for (int y = 0; y < sy; ++y) {for (const int i : events[y]) {auto v = seg.get(X[i]);v.l -= y_p[Y[i]];--v.cl;v.u += y_p[Y[i]];++v.cu;seg.set(X[i], v);}const auto product = seg.fold();const i64 all_sum = calc_sum(product, y);auto f = [&](M1::Type v) {const i64 sum = calc_sum(v, y);return sum <= all_sum / 2;};const int max_right = seg.calc_max_right(0, f);if (max_right != 0) points.push_back({max_right - 1, y});if (max_right != sx) points.push_back({max_right, y});}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(sx);SegmentTree<M3> seg_s(sx), seg_c(sx);std::vector<std::vector<int>> event_a(sy), event_q(sy);for (int i = 0; i < N; ++i) event_a[Y[i]].push_back(i);for (int i = 0; i < M; ++i) event_q[points[i].second].push_back(i);for (int y = 0; y < sy; ++y) {for (const int i : event_a[y]) {const int x = X[i];seg_f.set(x, M2::op(seg_f.get(x), {x_p[x], -((i64)x_p[x] * y_p[y])}));seg_s.set(x, seg_s.get(x) + y_p[y]);seg_c.set(x, seg_c.get(x) + 1);}for (const int i : event_q[y]) {const int x = points[i].first;i64 sum = (seg_c.fold(0, x) * y_p[y] - seg_s.fold(0, x)) * x_p[x];const auto f = seg_f.fold(0, x);sum -= y_p[y] * 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;}