結果
| 問題 | No.1074 増殖 |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-06-05 22:45:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 10,959 bytes |
| コンパイル時間 | 1,908 ms |
| コンパイル使用メモリ | 166,384 KB |
| 最終ジャッジ日時 | 2025-01-10 22:48:44 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | TLE * 3 |
| other | TLE * 12 |
ソースコード
#define CPP17#include <limits>#include <initializer_list>#include <utility>#include <bitset>#include <tuple>#include <type_traits>#include <functional>#include <string>#include <array>#include <deque>#include <list>#include <queue>#include <stack>#include <vector>#include <map>#include <set>#include <unordered_map>#include <unordered_set>#include <iterator>#include <algorithm>#include <complex>#include <random>#include <numeric>#include <iostream>#include <iomanip>#include <sstream>#include <regex>#include <cassert>#include <cstddef>#ifdef CPP17#include <variant>#endif// Yay!!#define endl codeforces// macros for iterator#define ALL(v) std::begin(v), std::end(v)#define ALLR(v) std::rbegin(v), std::rend(v)// aliasusing ll = std::int64_t;using ull = std::uint64_t;using pii = std::pair<int, int>;using tii = std::tuple<int, int, int>;using pll = std::pair<ll, ll>;using tll = std::tuple<ll, ll, ll>;template <typename T> using vec = std::vector<T>;template <typename T> using vvec = vec<vec<T>>;// variadic min/maxtemplate <typename T> const T& var_min(const T &t) { return t; }template <typename T> const T& var_max(const T &t) { return t; }template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }// variadic chmin/chmaxtemplate <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }// multi demension arraytemplate <typename T, std::size_t Head, std::size_t... Tail> struct multi_dim_array { using type = std::array<typename multi_dim_array<T, Tail...>::type, Head>; };template <typename T, std::size_t Head> struct multi_dim_array<T, Head> { using type = std::array<T, Head>; };template <typename T, std::size_t... Args> using mdarray = typename multi_dim_array<T, Args...>::type;#ifdef CPP17// fill containertemplate <typename T, typename F, typename... Args>void fill_seq(T &t, F f, Args... args) { if constexpr (std::is_invocable<F, Args...>::value) { t = f(args...); } else { for (ssize_t i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i); } }#endif// make multi dimension vectortemplate <typename T> vec<T> make_v(ssize_t sz) { return vec<T>(sz); }template <typename T, typename... Tail> auto make_v(ssize_t hs, Tail&&... ts) { auto v = std::move(make_v<T>(std::forward<Tail>(ts)...)); return vec<decltype(v)>(hs, v); }// initnamespace init__ {struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } }init_io;}namespace utility {template <typename T>using validate_integer = typename std::enable_if<std::is_integral<T>::value, ll>::type;template <typename T>auto popcount(T n) -> validate_integer<T> {return __builtin_popcount(n);}// 0 indexedtemplate <typename T>auto msb(T n) -> validate_integer<T> {return 64 - __builtin_clzll(n) - 1;}template <typename T>constexpr auto ceil_pow2(T s) -> validate_integer<T> {ll ret = 1;while (ret < s) ret *= 2;return ret;}}namespace utility {struct has_id_ele {template <typename T>auto operator ()(T &&t) -> decltype(T::id_ele(), std::true_type()) { return std::true_type(); }std::false_type operator ()(...) { return std::false_type(); }};struct has_merge {template <typename T>auto operator ()(T &&t) -> decltype(T::merge(std::declval<T>(), std::declval<T>()), std::true_type()) { return std::true_type(); }std::false_type operator ()(...) { return std::false_type(); }};struct has_apply {template <typename M, typename Op>auto operator ()(M &&m, Op &&op) -> decltype(m.apply(op), std::true_type()) { return std::true_type(); }std::false_type operator ()(...) { return std::false_type(); }};template <typename F, typename... Args>using callable = std::is_same<typename std::invoke_result<F, Args...>::type, std::true_type>;template <typename M>using is_monoid = std::conjunction<callable<has_id_ele, M>, callable<has_merge, M>>;template <typename M, typename Op>using enable_apply = callable<has_apply, M, Op>;}namespace segtree {template <typename M, typename Op>class LazySegmentTree {static_assert(utility::is_monoid<M>::value, "M must be monoid.");static_assert(utility::is_monoid<Op>::value, "Op must be monoid.");static_assert(utility::enable_apply<M, Op>::value, "Op is not operator of M.");using size_type = ssize_t;struct segment {M m;Op op;bool has_lazy;segment(M m = M::id_ele()) : m(m), op(Op::id_ele()), has_lazy(false) { }void update_op(Op o) {op = Op::merge(op, o);has_lazy = true;}void apply() {if (!has_lazy) return;m.apply(op);init_op();}void init_op() {op = Op::id_ele();has_lazy = false;}};vec<segment> segs;size_type height;void push(size_type idx) {auto &seg = segs[idx];if (!seg.has_lazy) return;auto tmp = seg.op;seg.apply();for (int i = 0; i < 2; i++) {auto cidx = 2 * idx + i;if (2 * size() <= cidx) break;auto &cseg = segs[cidx];cseg.update_op(tmp);}}void propagate_from_top(size_type idx) {for (int i = height; 1 <= i; i--) push(idx >> i);}void update_from_bottom(size_type idx) {while (true) {auto pidx = idx / 2;if (pidx == 0) break;push(2 * pidx);push(2 * pidx + 1);segs[pidx].m = M::merge(segs[2 * pidx].m, segs[2 * pidx + 1].m);idx = pidx;}}size_type get_endpoint_seg(size_type i) {i += size();return i / (i & -i);}public:template <typename T>LazySegmentTree(const vec<T> &v) {size_type sz = utility::ceil_pow2(v.size());segs.resize(sz * 2);height = utility::msb(sz);for (auto i = 0; i < v.size(); i++) segs[i + sz] = v[i];for (auto i = sz - 1; 1 <= i; i--) segs[i] = M::merge(segs[2 * i].m, segs[2 * i + 1].m);}size_type size() const {return segs.size() / 2;}template <typename T>void update_query(size_type ql, size_type qr, const T &t) {Op op(t);auto l0 = get_endpoint_seg(ql);auto r0 = get_endpoint_seg(qr);propagate_from_top(l0);propagate_from_top(r0);size_type lnode = ql + size(), rnode = qr + size();while (lnode < rnode) {if (lnode & 1) {segs[lnode].update_op(op);push(lnode);lnode++;}if (rnode & 1) {rnode--;segs[rnode].update_op(op);push(rnode);}lnode /= 2;rnode /= 2;}update_from_bottom(l0);update_from_bottom(r0);}M get_query(ll ql, ll qr) {auto ret = M::id_ele();auto l0 = get_endpoint_seg(ql);auto r0 = get_endpoint_seg(qr);propagate_from_top(l0);propagate_from_top(r0);size_type lnode = ql + size(), rnode = qr + size();while (lnode < rnode) {if (lnode & 1) {push(lnode);ret = M::merge(segs[lnode].m, ret);lnode++;}if (rnode & 1) {rnode--;push(rnode);ret = M::merge(ret, segs[rnode].m);}lnode /= 2;rnode /= 2;}return ret;}};}namespace utility {template <typename T>struct Compressor {using size_type = ssize_t;Compressor(vec<T> arg) : v(std::move(arg)) {std::sort(ALL(v));auto ite = std::unique(ALL(v));v.erase(ite, v.end());}const T& operator [](size_type i) const {return v[i];}size_type get(const T &t) const {return std::distance(v.begin(),std::lower_bound(ALL(v), t));}size_type size() const {return v.size();}template <typename U = T>vec<U> compress(const vec<T> &v) const {vec<U> ret(v.size());for (size_type i = 0; i < v.size(); i++) ret[i] = get(v[i]);return ret;}private:vec<T> v;};};const ssize_t SIZE = 20010;struct Op {Op() { }static Op id_ele() { return Op(); }static Op merge(Op a, Op b) { return Op(); }};struct M {ll l, r;pll rng;M(ll l, ll r, pll rng) : l(l), r(r), rng(rng) { }static M id_ele() { return M(-SIZE, -SIZE, pll(-SIZE, -SIZE)); }static M merge(M a, M b) {if (b.l == -SIZE) return a;if (a.l == -SIZE) return b;ll l = std::min(a.l, b.l);ll r = std::max(a.r, b.r);pll rng = merge_rng(a.rng, b.rng);return M(l, r, rng);}void apply(Op o) { rng = pll(l, r); }static ll get_rng_l(ll a, ll b) {if (a == -SIZE) return b;if (b == -SIZE) return a;return std::min(a, b);}static ll get_rng_r(ll a, ll b) {if (a == -SIZE) return b;if (b == -SIZE) return a;return std::max(a, b);}static pll merge_rng(pll p, pll q) {auto [ a, b ] = p;auto [ c, d ] = q;return pll(get_rng_l(a, c), get_rng_r(b, d));}};int main() {using square = std::tuple<ll, ll, ll, ll>;using lst_type = segtree::LazySegmentTree<M, Op>;ll n;std::cin >> n;vec<M> init_v;init_v.reserve(2 * SIZE);vec<square> sv(n);for (auto &&e : sv) {ll a, b, c, d;std::cin >> a >> b >> c >> d;e = square(a, b, c, d);}for (ll i = 0; i < 2 * SIZE; i++) init_v.push_back(M(i, i + 1, pll(-SIZE, -SIZE)));vec<ll> ans(n);auto len = [](pll p) {auto [ a, b ] = p;return b - a;};for (ll y = -SIZE; y <= SIZE; y++) {lst_type lst(init_v);for (ll i = 0; i < n; i++) {auto [ xa, ya, xb, yb ] = sv[i];if (!(ya <= y && y < yb)) continue;for (ll y = ya; y < yb; y++) {pll a = lst.get_query(0, 2 * SIZE).rng;lst.update_query(xa + SIZE, xb + SIZE, Op());pll b = lst.get_query(0, 2 * SIZE).rng;ans[i] += len(b) - len(a);}}}for (ll e : ans) std::cout << e << "\n";return 0;}