結果

問題 No.1625 三角形の質問
コンテスト
ユーザー cho435
提出日時 2026-03-18 16:50:35
言語 C++23(gnu拡張)
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 1,424 ms / 6,000 ms
コード長 6,287 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,560 ms
コンパイル使用メモリ 401,616 KB
実行使用メモリ 137,360 KB
最終ジャッジ日時 2026-03-18 16:51:06
合計ジャッジ時間 27,188 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using ll = long long;
#define rep(i, s, t) for (ll i = s; i < (ll)(t); i++)
#define all(x) begin(x), end(x)
template <class T> bool chmin(T& x, T y) {
	return x > y ? (x = y, true) : false;
}
template <class T> bool chmax(T& x, T y) {
	return x < y ? (x = y, true) : false;
}

// Bit Vector (for 64-bit non-negative integer)
struct bit_vector {
	// block: bit vector
	// count: the number of 1 within each block
	unsigned int n, zeros;
	vector<unsigned long long> block;
	vector<unsigned int> count;

	// constructor
	bit_vector() {};
	bit_vector(const unsigned int num)
		: n(num),
		  block(((num + 1) >> 6) + 1, 0),
		  count(((num + 1) >> 6) + 1, 0) {};

	// set val(0 or 1) onto i-th bit, get i-th bit of val(0 or 1)
	void set(const unsigned int i, const unsigned long long val = 1LL) {
		assert((i >> 6) < block.size());
		block[i >> 6] |= (val << (i & 63));
	}
	unsigned int get(const unsigned int i) const {
		assert((i >> 6) < block.size());
		return (unsigned int)(block[i >> 6] >> (i & 63)) & 1;
	}
	void build() {
		for (unsigned int i = 1; i < block.size(); i++) {
			count[i] = count[i - 1] + __builtin_popcountll(block[i - 1]);
		}
		zeros = rank0(n);
	}

	// the number of 1 in [0, i)
	unsigned int rank1(const unsigned int i) const {
		assert((i >> 6) < count.size());
		return count[i >> 6] + __builtin_popcountll(
								   block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
	}
	// the number of 1 in [i, j)
	unsigned int rank1(const unsigned int i, const unsigned int j) const {
		return rank1(j) - rank1(i);
	}
	// the number of 0 in [0, i)
	unsigned int rank0(const unsigned int i) const {
		return i - rank1(i);
	}
	// the number of 0 in [i, j)
	unsigned int rank0(const unsigned int i, const unsigned int j) const {
		return rank0(j) - rank0(i);
	}
	// the number of 0 in [0, n)
	unsigned int rank0() const {
		return zeros;
	}
};

// https://trap.jp/post/2713/
template <typename T, typename S, auto op, auto e>
struct wavelet_matrix {
	using segtree = atcoder::segtree<S, op, e>;
	int n, log_n;
	vector<bit_vector> bit;
	vector<segtree> seg;
	wavelet_matrix(const vector<T>& v) : n(v.size()), log_n(0) {
		T max_v = *max_element(v.begin(), v.end());
		while (max_v > 0) log_n++, max_v >>= 1;
		bit.assign(log_n, bit_vector(n));
		seg.assign(log_n, segtree(n));
		vector<int> left(n), right(n), ord(n);
		iota(ord.begin(), ord.end(), 0);
		for (int level = log_n - 1; level >= 0; level--) {
			int idx0 = 0, idx1 = 0;
			for (int i = 0; i < n; i++) {
				if ((v[ord[i]] >> level) & 1) {
					bit[level].set(i);
					right[idx1++] = ord[i];
				} else {
					left[idx0++] = ord[i];
				}
			}
			bit[level].build();
			ord.swap(left);
			for (int i = 0; i < idx1; i++) ord[idx0 + i] = right[i];
		}
	}

	void set(int idx, const S& seg_val) {
		for (int level = log_n - 1; level >= 0; level--) {
			if (bit[level].get(idx)) {
				idx = idx + bit[level].rank0() - bit[level].rank0(idx);
			} else {
				idx = bit[level].rank0(idx);
			}
			seg[level].set(idx, seg_val);
		}
	}

	S rectangle_iter(int i0, int i1, const T& j0, const T& j1) const {
		int it = log_n - 1;

		// 1. 分岐点まで下る
		while (it >= 0 && (((j0 ^ j1) >> it) & 1) == 0) {
			int z0 = bit[it].rank0(i0);
			int z1 = bit[it].rank0(i1);

			if (((j0 >> it) & 1) == 0) {
				i0 = z0;
				i1 = z1;
			} else {
				int med = bit[it].rank0();
				i0 = med + i0 - z0;
				i1 = med + i1 - z1;
			}
			it--;
		}

		int l0 = 0, l1 = 0, r0 = 0, r1 = 0;

		// 2. 左右に分割
		if (it >= 0) {
			int z0 = bit[it].rank0(i0);
			int z1 = bit[it].rank0(i1);
			l0 = z0;
			l1 = z1;
			int med = bit[it].rank0();
			r0 = med + i0 - z0;
			r1 = med + i1 - z1;
			it--;
		}

		S res = e();

		// 3. 左側の境界線（j0）のイテレータ相当
		int it_l = it;
		while (it_l >= 0) {
			int z0 = bit[it_l].rank0(l0);
			int z1 = bit[it_l].rank0(l1);
			int med = bit[it_l].rank0();
			int o0 = med + l0 - z0;
			int o1 = med + l1 - z1;

			if (((j0 >> it_l) & 1) == 0) {
				res = op(res, seg[it_l].prod(o0, o1));
				l0 = z0;
				l1 = z1;
			} else {
				l0 = o0;
				l1 = o1;
			}
			it_l--;
		}

		// 4. 右側の境界線（j1）のイテレータ相当
		int it_r = it;
		while (it_r >= 0) {
			int z0 = bit[it_r].rank0(r0);
			int z1 = bit[it_r].rank0(r1);
			int med = bit[it_r].rank0();
			int o0 = med + r0 - z0;
			int o1 = med + r1 - z1;

			if (((j1 >> it_r) & 1) == 0) {
				r0 = z0;
				r1 = z1;
			} else {
				res = op(res, seg[it_r].prod(z0, z1));
				r0 = o0;
				r1 = o1;
			}
			it_r--;
		}

		return res;
	}
};

pair<pair<int, int>, ll> get_tri() {
	int a, b, c, d, e, f;
	cin >> a >> b >> c >> d >> e >> f;
	ll dx1 = a - c, dy1 = b - d, dx2 = a - e, dy2 = b - f;
	return {{min({a, c, e}), max({a, c, e})}, abs(dx1 * dy2 - dx2 * dy1)};
}

void solve() {
	int n, q;
	cin >> n >> q;
	vector<pair<int, int>> ps;
	vector<pair<pair<int, int>, ll>> tris(n);
	rep(i, 0, n) {
		tris[i] = get_tri();
		ps.push_back(tris[i].first);
	}
	vector<int> tp(q);
	vector<pair<pair<int, int>, ll>> tris_add(q);
	vector<pair<int, int>> qs(q);
	rep(i, 0, q) {
		cin >> tp[i];
		if (tp[i] == 1) {
			tris_add[i] = get_tri();
			ps.push_back(tris_add[i].first);
		} else {
			cin >> qs[i].first >> qs[i].second;
		}
	}
	sort(all(ps));
	ps.erase(unique(all(ps)), ps.end());

	int m = ps.size();
	vector<int> y(m);
	rep(i, 0, m) y[i] = ps[i].second;
	wavelet_matrix<int, ll,
				   [](ll a, ll b) {
					   return max(a, b);
				   },
				   []() {
					   return -1;
				   }>
		wm(y);

	vector<ll> seg_init(m, -1);
	auto add_tri = [&](const pair<pair<int, int>, ll>& tri) {
		int idx = lower_bound(all(ps), tri.first) - ps.begin();
		assert(idx < m && ps[idx] == tri.first);
		if (chmax(seg_init[idx], tri.second)) wm.set(idx, tri.second);
	};

	rep(i, 0, n) add_tri(tris[i]);
	rep(i, 0, q) {
		if (tp[i] == 1) {
			add_tri(tris_add[i]);
		} else {
			auto [l, r] = qs[i];
			int l_idx = lower_bound(all(ps), make_pair(l, -1)) - ps.begin();
			int r_idx = lower_bound(all(ps), make_pair(r + 1, -1)) - ps.begin();
			cout << wm.rectangle_iter(l_idx, r_idx, l, r + 1) << "\n";
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << fixed << setprecision(15);
	int t = 1;
	// cin >> t;
	while (t--) solve();
}
0