結果
| 問題 | No.1625 三角形の質問 |
| コンテスト | |
| ユーザー |
 kwm_t
|
| 提出日時 | 2026-04-02 20:49:18 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 1,501 ms / 6,000 ms |
| コード長 | 5,398 bytes |
| 記録 | |
| コンパイル時間 | 6,705 ms |
| コンパイル使用メモリ | 391,900 KB |
| 実行使用メモリ | 141,380 KB |
| 最終ジャッジ日時 | 2026-04-03 10:39:31 |
| 合計ジャッジ時間 | 26,719 ms |
|
ジャッジサーバーID （参考情報） |
judge4_1 / judge5_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 19 |
コンパイルメッセージ
main.cpp:21:9: warning: '#pragma once' in main file [-Wpragma-once-outside-header]
21 | #pragma once
| ^~~~
ソースコード
#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; }
#pragma once
#include <vector>
#include <algorithm>
template <class S, S(*op)(S, S), S(*e)(), class C>
struct segtree2D_lite {
int H;
std::vector<C> ys;
std::vector<std::vector<C>> xs; // 各ノードのx座標
std::vector<std::vector<S>> seg; // 各ノードの1D segtree
std::vector<int> W;
std::vector<std::pair<C, C>> points;
segtree2D_lite() {}
void insert(C y, C x) {
points.emplace_back(y, x);
}
void build() {
// y座標圧縮
for (auto&[y, x] : points) ys.push_back(y);
std::sort(ys.begin(), ys.end());
ys.erase(std::unique(ys.begin(), ys.end()), ys.end());
H = 1 << ceil_pow2(ys.size());
xs.resize(2 * H);
seg.resize(2 * H);
W.resize(2 * H);
// 各ノードにxを配る
for (auto&[y0, x0] : points) {
int y = get_y(y0) + H;
while (y) {
xs[y].push_back(x0);
y >>= 1;
}
}
// 各ノードでx圧縮＋segtree構築
for (int i = 0; i < 2 * H; i++) {
auto& v = xs[i];
std::sort(v.begin(), v.end());
v.erase(std::unique(v.begin(), v.end()), v.end());
int sz = v.size();
int k = ceil_pow2(sz);
W[i] = 1 << k;
seg[i].assign(2 * W[i], e());
}
}
void set(C y0, C x0, S val) {
int y = get_y(y0) + H;
while (y) {
int xi = get_x(y, x0);
xi += W[y];
seg[y][xi] = op(seg[y][xi], val);
while (xi >>= 1) pull(y, xi);
y >>= 1;
}
}
S prod(C ly, C lx, C ry, C rx) {
int l = get_y(ly) + H;
int r = get_y(ry) + H;
S left = e(), right = e();
while (l < r) {
if (l & 1) left = op(left, query_x(l++, lx, rx));
if (r & 1) right = op(query_x(--r, lx, rx), right);
l >>= 1;
r >>= 1;
}
return op(left, right);
}
private:
int get_y(C y) {
return std::lower_bound(ys.begin(), ys.end(), y) - ys.begin();
}
int get_x(int node, C x) {
return std::lower_bound(xs[node].begin(), xs[node].end(), x) - xs[node].begin();
}
S query_x(int node, C lx, C rx) {
int l = std::lower_bound(xs[node].begin(), xs[node].end(), lx) - xs[node].begin();
int r = std::lower_bound(xs[node].begin(), xs[node].end(), rx) - xs[node].begin();
S left = e(), right = e();
l += W[node], r += W[node];
while (l < r) {
if (l & 1) left = op(left, seg[node][l++]);
if (r & 1) right = op(seg[node][--r], right);
l >>= 1;
r >>= 1;
}
return op(left, right);
}
void pull(int node, int i) {
seg[node][i] = op(seg[node][2 * i], seg[node][2 * i + 1]);
}
int ceil_pow2(int n) {
int x = 0;
while ((1U << x) < (unsigned int)n) x++;
return x;
}
};
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;
segtree2D_lite<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.insert(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.insert(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;
}