結果
問題 | No.1625 三角形の質問 |
ユーザー | KoD |
提出日時 | 2021-07-23 21:48:00 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,914 ms / 6,000 ms |
コード長 | 7,841 bytes |
コンパイル時間 | 2,620 ms |
コンパイル使用メモリ | 227,400 KB |
実行使用メモリ | 142,156 KB |
最終ジャッジ日時 | 2023-09-25 21:45:12 |
合計ジャッジ時間 | 28,972 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge13 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 71 ms
11,540 KB |
testcase_02 | AC | 578 ms
47,452 KB |
testcase_03 | AC | 724 ms
58,832 KB |
testcase_04 | AC | 450 ms
40,268 KB |
testcase_05 | AC | 1,120 ms
82,568 KB |
testcase_06 | AC | 1,828 ms
119,056 KB |
testcase_07 | AC | 1,832 ms
119,404 KB |
testcase_08 | AC | 1,862 ms
117,808 KB |
testcase_09 | AC | 1,914 ms
120,728 KB |
testcase_10 | AC | 1,813 ms
115,104 KB |
testcase_11 | AC | 1,883 ms
119,376 KB |
testcase_12 | AC | 1,873 ms
119,896 KB |
testcase_13 | AC | 1,863 ms
118,656 KB |
testcase_14 | AC | 1,868 ms
118,632 KB |
testcase_15 | AC | 1,849 ms
116,212 KB |
testcase_16 | AC | 236 ms
45,296 KB |
testcase_17 | AC | 579 ms
113,476 KB |
testcase_18 | AC | 87 ms
12,656 KB |
testcase_19 | AC | 720 ms
142,156 KB |
ソースコード
#include <bits/stdc++.h> using i32 = std::int32_t; using u32 = std::uint32_t; using i64 = std::int64_t; using u64 = std::uint64_t; using i128 = __int128_t; using u128 = __uint128_t; using isize = std::ptrdiff_t; using usize = std::size_t; class rep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { ++itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr rep(const usize first, const usize last) noexcept : first(first), last(std::max(first, last)) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; template <class T, T Div = 2> constexpr T INFTY = std::numeric_limits<T>::max() / Div; class revrep { struct Iter { usize itr; constexpr Iter(const usize pos) noexcept : itr(pos) {} constexpr void operator++() noexcept { --itr; } constexpr bool operator!=(const Iter& other) const noexcept { return itr != other.itr; } constexpr usize operator*() const noexcept { return itr; } }; const Iter first, last; public: explicit constexpr revrep(const usize first, const usize last) noexcept : first(last - 1), last(std::min(first, last) - 1) {} constexpr Iter begin() const noexcept { return first; } constexpr Iter end() const noexcept { return last; } }; constexpr u64 ceil_log2(const u64 x) { u64 e = 0; while (((u64)1 << e) < x) ++e; return e; } template <class Monoid> class SegmentTree { using M = Monoid; usize internal_size, seg_size; std::vector<M> data; void fetch(const usize k) { data[k] = data[2 * k] + data[2 * k + 1]; } public: explicit SegmentTree(const usize size = 0, const M& value = M::zero()) : SegmentTree(std::vector<M>(size, value)) {} explicit SegmentTree(const std::vector<M>& vec) : internal_size(vec.size()) { seg_size = 1 << ceil_log2(internal_size); data = std::vector<M>(2 * seg_size, M::zero()); for (const usize i : rep(0, internal_size)) data[seg_size + i] = vec[i]; for (const usize i : revrep(1, seg_size)) fetch(i); } usize size() const { return internal_size; } void assign(usize i, const M& value) { assert(i < internal_size); i += seg_size; data[i] = value; while (i > 1) { i >>= 1; fetch(i); } } M fold() const { return data[1]; } M fold(usize l, usize r) const { assert(l <= r and r <= internal_size); l += seg_size; r += seg_size; M ret_l = M::zero(), ret_r = M::zero(); while (l < r) { if (l & 1) ret_l = ret_l + data[l++]; if (r & 1) ret_r = data[--r] + ret_r; l >>= 1; r >>= 1; } return ret_l + ret_r; } template <class F> usize max_right(usize l, const F& f) const { assert(l <= internal_size); assert(f(M::zero())); if (l == internal_size) return internal_size; l += seg_size; M sum = M::zero(); do { while (!(l & 1)) l >>= 1; if (!f(sum + data[l])) { while (l < seg_size) { l = 2 * l; if (f(sum + data[l])) sum = sum + data[l++]; } return l - seg_size; } sum = sum + data[l++]; } while ((l & -l) != l); return internal_size; } template <class F> usize min_left(usize r, const F& f) const { assert(r <= internal_size); assert(f(M::zero())); if (r == 0) return 0; r += seg_size; M sum = M::zero(); do { r -= 1; while (r > 1 and (r & 1)) r >>= 1; if (!f(data[r] + sum)) { while (r < seg_size) { r = 2 * r + 1; if (f(data[r] + sum)) sum = data[r--] + sum; } return r + 1 - seg_size; } sum = data[r] + sum; } while ((r & -r) != r); return 0; } }; template <class T> using Vec = std::vector<T>; struct Max { i64 max; static Max zero() { return Max{-INFTY<i64>}; } Max operator+(const Max& other) const { return Max{std::max(max, other.max)}; } }; std::array<i64, 3> get_triangle() { std::array<std::array<i64, 2>, 3> arr; for (auto& v : arr) { for (auto& x : v) { std::cin >> x; } } std::sort(arr.begin(), arr.end()); std::array<i64, 3> ret; ret[0] = arr[0][0]; ret[1] = arr[2][0]; ret[2] = std::abs((arr[1][0] - arr[0][0]) * (arr[2][1] - arr[0][1]) - (arr[1][1] - arr[0][1]) * (arr[2][0] - arr[0][0])); return ret; } void main_() { usize N, Q; std::cin >> N >> Q; Vec<std::array<i64, 3>> pts(N); for (auto& arr : pts) { arr = get_triangle(); } Vec<std::pair<usize, bool>> query(N + Q); for (const auto i : rep(0, N)) { query[i] = std::make_pair(i, false); } Vec<std::array<i64, 2>> range; for (const auto i : rep(0, Q)) { usize t; std::cin >> t; if (t == 1) { query[N + i] = std::make_pair(pts.size(), false); pts.emplace_back() = get_triangle(); } else { query[N + i] = std::make_pair(range.size(), true); auto& [l, r] = range.emplace_back(); std::cin >> l >> r; } } Vec<i64> xs; xs.reserve(pts.size()); for (const auto& arr : pts) { xs.push_back(arr[0]); } std::sort(xs.begin(), xs.end()); xs.erase(std::unique(xs.begin(), xs.end()), xs.end()); const auto Xlen = xs.size(); Vec<Vec<i64>> ys(2 * Xlen); for (const auto& arr : pts) { usize x = Xlen + std::lower_bound(xs.begin(), xs.end(), arr[0]) - xs.begin(); while (x > 0) { ys[x].push_back(arr[1]); x >>= 1; } } for (auto& vec : ys) { std::sort(vec.begin(), vec.end()); vec.erase(std::unique(vec.begin(), vec.end()), vec.end()); } Vec<SegmentTree<Max>> seg(2 * Xlen); for (const auto i : rep(1, 2 * Xlen)) { seg[i] = SegmentTree<Max>(ys[i].size()); } for (const auto& [i, f] : query) { if (f) { const auto& [l, r] = range[i]; usize xl = Xlen + std::lower_bound(xs.begin(), xs.end(), l) - xs.begin(); usize xr = 2 * Xlen; i64 ans = -1; while (xl < xr) { if (xl & 1) { ans = std::max( ans, seg[xl].fold(0, std::upper_bound(ys[xl].begin(), ys[xl].end(), r) - ys[xl].begin()).max); xl += 1; } if (xr & 1) { xr -= 1; ans = std::max( ans, seg[xr].fold(0, std::upper_bound(ys[xr].begin(), ys[xr].end(), r) - ys[xr].begin()).max); } xl >>= 1; xr >>= 1; } std::cout << ans << '\n'; } else { const auto& arr = pts[i]; usize x = Xlen + std::lower_bound(xs.begin(), xs.end(), arr[0]) - xs.begin(); while (x > 0) { const usize y = std::lower_bound(ys[x].begin(), ys[x].end(), arr[1]) - ys[x].begin(); seg[x].assign(y, Max{std::max(seg[x].fold(y, y + 1).max, arr[2])}); x >>= 1; } } } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); main_(); return 0; }