#1156159 (C++23) No.1625 三角形の質問

提出ソース

結果

問題	No.1625 三角形の質問
コンテスト
ユーザー	kwm_t
提出日時	2026-04-02 21:07:19
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	1,027 ms / 6,000 ms
コード長	7,213 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,122 ms
コンパイル使用メモリ	392,336 KB
実行使用メモリ	141,580 KB
最終ジャッジ日時	2026-04-03 10:39:04
合計ジャッジ時間	22,200 ms
ジャッジサーバーID （参考情報）	judge4_0 / judge2_0

このコードへのチャレンジ
（要ログイン）

ファイルパターン	結果
sample	AC * 1
other	AC * 19

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A &a, const B &b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A &a, const B &b) { if (a > b) { a = b; return true; } return false; }

#ifndef KWM_T_SEGTREE_SEGTREE_2D_HPP
#define KWM_T_SEGTREE_SEGTREE_2D_HPP

#include <vector>
#include <algorithm>

/**
 * @brief 2次元セグメント木（座標圧縮・静的）
 *
 * 縦方向にセグ木を持ち、各ノードに横方向のセグ木を持つ構造
 *
 * 典型用途:
 *   - 点更新 + 矩形クエリ
 *   - 座標圧縮が必要な2D range query
 *
 * 計算量:
 *   - build: O(N log N)
 *   - update: O(log^2 N)
 *   - query: O(log^2 N)
 *
 * @tparam S モノイドの型
 * @tparam op 二項演算 (S, S) -> S
 * @tparam e 単位元 () -> S
 * @tparam C 座標型（int / long long など）
 *
 * 制約 / 注意:
 *   - 事前に add_point() を呼び、build() が必要
 *   - update() は build() 後に使用
 *   - クエリは半開区間 [li, ri) × [lj, rj)
 *
 * 使用例:
 *   SegTree2D<ll, op, e, int> seg;
 *   seg.add_point(i, j);
 *   seg.build();
 *   seg.update(i, j, val);
 *   seg.query(li, lj, ri, rj);
 *
 * verified:
 *   https://atcoder.jp/contests/ABC266/submissions/74604159
 */
namespace kwm_t::segtree {

template <class S, S(*op)(S, S), S(*e)(), class C>
class segtree_2d {
private:
	int H;                                   // 縦セグ木サイズ（2冪）
	std::vector<C> coord_i;                  // i座標
	std::vector<std::vector<C>> coord_j;     // 各ノードのj座標
	std::vector<std::vector<S>> seg;         // 各ノードの横seg木
	std::vector<int> size_j;                 // 横seg木サイズ

	std::vector<std::pair<C, C>> points;     // (i, j)

public:
	segtree_2d() = default;

	/**
	 * @brief 点の登録（build前）
	 */
	void add_point(C i, C j) {
		points.emplace_back(i, j);
	}

	/**
	 * @brief 構築
	 */
	void build() {
		// i座標圧縮
		for (auto&[i, j] : points) coord_i.push_back(i);
		std::sort(coord_i.begin(), coord_i.end());
		coord_i.erase(std::unique(coord_i.begin(), coord_i.end()), coord_i.end());

		H = 1 << ceil_pow2((int)coord_i.size());
		coord_j.resize(2 * H);
		seg.resize(2 * H);
		size_j.resize(2 * H);

		// 各ノードにjを配布
		for (auto&[i0, j0] : points) {
			int i = get_i(i0) + H;
			while (i > 0) {
				coord_j[i].push_back(j0);
				i >>= 1;
			}
		}

		// 各ノードでj圧縮＋seg木構築
		for (int node = 0; node < 2 * H; node++) {
			auto& v = coord_j[node];
			std::sort(v.begin(), v.end());
			v.erase(std::unique(v.begin(), v.end()), v.end());

			int sz = (int)v.size();
			int k = ceil_pow2(sz);
			size_j[node] = 1 << k;
			seg[node].assign(2 * size_j[node], e());
		}
	}

	/**
	 * @brief 点更新（モノイド演算）
	 */
	void set(C i0, C j0, S val) {
		int i = get_i(i0) + H;
		while (i > 0) {
			int j_idx = get_j(i, j0);
			int idx = j_idx + size_j[i];

			seg[i][idx] = op(seg[i][idx], val);

			while (idx >>= 1) {
				pull(i, idx);
			}
			i >>= 1;
		}
	}

	/**
	 * @brief 矩形クエリ [li, ri) × [lj, rj)
	 */
	S prod(C li, C lj, C ri, C rj) {
		int l = get_i(li) + H;
		int r = get_i(ri) + H;

		S res_l = e(), res_r = e();

		while (l < r) {
			if (l & 1) res_l = op(res_l, query_j(l++, lj, rj));
			if (r & 1) res_r = op(query_j(--r, lj, rj), res_r);
			l >>= 1;
			r >>= 1;
		}
		return op(res_l, res_r);
	}

private:
	// i座標取得
	int get_i(C i) const {
		return std::lower_bound(coord_i.begin(), coord_i.end(), i) - coord_i.begin();
	}

	// j座標取得
	int get_j(int node, C j) const {
		return std::lower_bound(coord_j[node].begin(), coord_j[node].end(), j) - coord_j[node].begin();
	}

	// 横方向クエリ
	S query_j(int node, C lj, C rj) {
		int l = std::lower_bound(coord_j[node].begin(), coord_j[node].end(), lj) - coord_j[node].begin();
		int r = std::lower_bound(coord_j[node].begin(), coord_j[node].end(), rj) - coord_j[node].begin();

		S res_l = e(), res_r = e();
		l += size_j[node];
		r += size_j[node];

		while (l < r) {
			if (l & 1) res_l = op(res_l, seg[node][l++]);
			if (r & 1) res_r = op(seg[node][--r], res_r);
			l >>= 1;
			r >>= 1;
		}
		return op(res_l, res_r);
	}

	// 親更新
	void pull(int node, int idx) {
		seg[node][idx] = op(seg[node][2 * idx], seg[node][2 * idx + 1]);
	}

	// ceil(log2(n))
	int ceil_pow2(int n) const {
		int x = 0;
		while ((1U << x) < (unsigned int)n) x++;
		return x;
	}
};

} // namespace kwm_t::segtree

#endif // KWM_T_SEGTREE_SEGTREE_2D_HPP



long long calcS(long long a, long long b, long long c, long long d, long long e, long long f) {
	c -= a; d -= b;
	e -= a; f -= b;
	return abs(c*f - d * e);
}


long long op(long long a, long long b) { return std::max(a, b); }
long long e() { return -1; }


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, q;
	cin >> n >> q;

	kwm_t::segtree::segtree_2d<long long, op, e, int> seg;

	vector<array<long long, 6>> a(n);
	vector<vector<long long>> qe(q);

	// 入力 + insert
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 6; j++) cin >> a[i][j];

		int l = min({ a[i][0], a[i][2], a[i][4] });
		int r = max({ a[i][0], a[i][2], a[i][4] });
		seg.add_point(l, r);
	}

	// クエリ読み込み
	for (int i = 0; i < q; i++) {
		int type;
		cin >> type;

		if (type == 1) {
			qe[i].resize(7);
			qe[i][0] = type;
			for (int j = 1; j <= 6; j++) cin >> qe[i][j];

			int l = min({ qe[i][1], qe[i][3], qe[i][5] });
			int r = max({ qe[i][1], qe[i][3], qe[i][5] });
			seg.add_point(l, r);
		}
		else {
			qe[i].resize(3);
			qe[i][0] = type;
			cin >> qe[i][1] >> qe[i][2];
		}
	}

	seg.build();

	// 三角形の面積 *2
	auto area2 = [&](long long x1, long long y1, long long x2, long long y2, long long x3, long long y3) {
		long long dx1 = x2 - x1;
		long long dx2 = x3 - x1;
		long long dy1 = y2 - y1;
		long long  dy2 = y3 - y1;
		return abs(dx1 * dy2 - dx2 * dy1);
	};

	// 初期追加
	for (int i = 0; i < n; i++) {
		int l = min({ a[i][0], a[i][2], a[i][4] });
		int r = max({ a[i][0], a[i][2], a[i][4] });

		long long  val = area2(
			a[i][0], a[i][1],
			a[i][2], a[i][3],
			a[i][4], a[i][5]
		);

		seg.set(l, r, val);
	}

	// クエリ処理
	for (int i = 0; i < q; i++) {
		if (qe[i][0] == 1) {
			int l = min({ qe[i][1], qe[i][3], qe[i][5] });
			int r = max({ qe[i][1], qe[i][3], qe[i][5] });

			long long  val = area2(
				qe[i][1], qe[i][2],
				qe[i][3], qe[i][4],
				qe[i][5], qe[i][6]
			);

			seg.set(l, r, val);
		}
		else {
			int l = qe[i][1];
			int r = qe[i][2];

			cout << seg.prod(l, l, r + 1, r + 1) << '\n';
		}
	}

	return 0;
}

yukicoder

結果

ソースコード