結果

問題 No.1625 三角形の質問
コンテスト
ユーザー cho435
提出日時 2026-03-18 21:27:14
言語 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  
実行時間 932 ms / 6,000 ms
コード長 7,714 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,527 ms
コンパイル使用メモリ 402,068 KB
実行使用メモリ 90,144 KB
最終ジャッジ日時 2026-03-18 21:27:38
合計ジャッジ時間 21,982 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

namespace cho {
struct bit_vector {
	int zeros;
	std::vector<uint64_t> block;
	std::vector<int> count;
	bit_vector() {};
	bit_vector(const int num)
		: zeros(num),
		  block(((num + 63) >> 6), 0),
		  count(((num + 63) >> 6), 0) {};
	void set(const int i) {
		assert((i >> 6) < (int)block.size());
		block[i >> 6] |= (1ULL << (i & 63));
	}
	bool operator[](int i) const {
		assert((i >> 6) < (int)block.size());
		return (block[i >> 6] >> (i & 63)) & 1;
	}
	void build() {
		for (int i = 1; i < (int)block.size(); i++) {
			count[i] = count[i - 1] + std::popcount(block[i - 1]);
		}
		zeros -= count.back() + std::popcount(block.back());
	}
	int rank1(const int i) const {
		assert((i >> 6) < (int)block.size());
		return count[i >> 6] +
			   std::popcount(block[i >> 6] & ((1ULL << (i & 63)) - 1ULL));
	}
	int rank0(const int i) const {
		return i - rank1(i);
	}
	int rank0() const {
		return zeros;
	}
};

template <typename S, auto op, auto e, typename T, int MAXLOG>
struct segtree_on_wavelet_matrix {
	using segtree = atcoder::segtree<S, op, e>;
	int n;
	std::vector<bit_vector> bit;
	std::vector<segtree> seg;
	segtree_on_wavelet_matrix(const std::vector<T>& v)
		: n(v.size()), bit(MAXLOG, bit_vector(n)), seg(MAXLOG, segtree(n)) {
		std::vector<int> left(n), right(n), ord(n);
		std::iota(ord.begin(), ord.end(), 0);
		for (int level = MAXLOG - 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();
			swap(ord, left);
			for (int i = 0; i < idx1; i++) ord[idx0 + i] = right[i];
		}
	}

	T k_th_smallest(int l, int r, int k) {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k < r - l);
		T res = 0;
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (r0 - l0 <= k) {
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
				k -= r0 - l0;
				res |= T(1) << level;
			} else {
				l = l0, r = r0;
			}
		}
		return res;
	}
	T k_th_largest(int l, int r, int k) {
		return k_th_smallest(l, r, r - l - k - 1);
	}
	// K個より多くなるかも
	S bottom_k_sum(int l, int r, int k) {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k <= r - l);
		if (l == r || k == 0) return e();
		S res = 0;
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			if (r0 - l0 <= k) {
				res = op(res, seg[level].prod(l0, r0));
				k -= r0 - l0;
				l += bit[level].rank0() - l0;
				r += bit[level].rank0() - r0;
			} else {
				l = l0, r = r0;
			}
		}
		if (k > 0 && l < r) {
			res = op(res, seg[0].prod(l, r));
		}
		return res;
	}
	// K個より多くなるかも
	S top_k_sum(int l, int r, int k) {
		assert(0 <= l && l <= r && r <= n);
		assert(0 <= k && k <= r - l);
		if (l == r || k == 0) return e();
		S res = 0;
		for (int level = MAXLOG - 1; level >= 0; level--) {
			int l0 = bit[level].rank0(l), r0 = bit[level].rank0(r);
			int l1 = l + bit[level].rank0() - l0;
			int r1 = r + bit[level].rank0() - r0;
			if (r1 - l1 <= k) {
				res = op(res, seg[level].prod(l1, r1));
				k -= r1 - l1;
				l = l0, r = r0;
			} else {
				l = l1, r = r1;
			}
		}
		if (k > 0 && l < r) {
			res = op(res, seg[0].prod(l, r));
		}
		return res;
	}

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

	S rectangle_sum(int i0, int i1, const T& j0, const T& j1) const {
		assert(0 <= i0 && i0 <= i1 && i1 <= n);
		assert(T(0) <= j0 && j0 <= j1 && j1 < T(1) << MAXLOG);
		if (i0 == i1 || j0 == j1) return e();
		int it = MAXLOG - 1;
		while (it >= 0 && (((j0 ^ j1) >> it) & 1) == 0) {
			if (((j0 >> it) & 1) == 0) {
				i0 = bit[it].rank0(i0);
				i1 = bit[it].rank0(i1);
			} else {
				i0 += bit[it].rank0() - bit[it].rank0(i0);
				i1 += bit[it].rank0() - bit[it].rank0(i1);
			}
			it--;
		}
		int l0 = 0, l1 = 0, r0 = 0, r1 = 0;
		if (it >= 0) {
			int z0 = bit[it].rank0(i0);
			int z1 = bit[it].rank0(i1);
			l0 = z0, l1 = z1;
			r0 = bit[it].rank0() + i0 - z0;
			r1 = bit[it].rank0() + i1 - z1;
			it--;
		}

		S res = e();
		int it_l = it, it_r = it;
		while (it_l >= 0) {
			int z0 = bit[it_l].rank0(l0);
			int z1 = bit[it_l].rank0(l1);
			if (((j0 >> it_l) & 1) == 0) {
				res = op(res, seg[it_l].prod(bit[it_l].rank0() + l0 - z0,
											 bit[it_l].rank0() + l1 - z1));
				l0 = z0, l1 = z1;
			} else {
				l0 += bit[it_l].rank0() - z0;
				l1 += bit[it_l].rank0() - z1;
			}
			it_l--;
		}
		res = op(res, seg[0].prod(l0, l1));
		while (it_r >= 0) {
			int z0 = bit[it_r].rank0(r0);
			int z1 = bit[it_r].rank0(r1);
			if (((j1 >> it_r) & 1) == 0) {
				r0 = z0, r1 = z1;
			} else {
				res = op(res, seg[it_r].prod(z0, z1));
				r0 += bit[it_r].rank0() - z0;
				r1 += bit[it_r].rank0() - z1;
			}
			it_r--;
		}
		return res;
	}
};
}  // namespace cho

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;
}

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)};
}

template <typename T>
struct compress {
	vector<T> xs;
	compress() {};
	compress(const vector<T>& vs) : xs(vs) {
		sort(all(xs));
		xs.erase(unique(all(xs)), xs.end());
	}
	int id(const T& x) const {
		return lower_bound(all(xs), x) - xs.begin();
	}
	T val(const int& i) const {
		return xs[i];
	}
	vector<int> to_ids(const vector<T>& vs) const {
		vector<int> res;
		res.reserve(vs.size());
		for (const T& v : vs) res.push_back(id(v));
		return res;
	}
};

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;
	compress<int> cy(y);
	cho::segtree_on_wavelet_matrix<ll,
								   [](ll a, ll b) {
									   return max(a, b);
								   },
								   []() {
									   return -1;
								   },
								   int, 18>
		wm(cy.to_ids(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_sum(l_idx, r_idx, cy.id(l), cy.id(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