結果

問題 No.1625 三角形の質問
コンテスト
ユーザー msm1993
提出日時 2021-07-28 11:03:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,455 ms / 6,000 ms
コード長 4,472 bytes
コンパイル時間 2,313 ms
コンパイル使用メモリ 186,088 KB
実行使用メモリ 172,416 KB
最終ジャッジ日時 2024-09-13 04:56:37
合計ジャッジ時間 37,175 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
struct segment_tree{
  int N;
  vector<long long> ST;
  segment_tree(){
  }
  segment_tree(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    ST = vector<long long>(N * 2 - 1, -1);
  }
  void update(int i, long long x){
    i += N - 1;
    ST[i] = max(ST[i], x);
    while (i > 0){
      i = (i - 1) / 2;
      ST[i] = max(ST[i], x);
    }
  }
  long long range_max(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      return -1;
    } else if (L <= l && r <= R){
      return ST[i];
    } else {
      int m = (l + r) / 2;
      return max(range_max(L, R, i * 2 + 1, l, m), range_max(L, R, i * 2 + 2, m, r));
    }
  }
  long long range_max(int L, int R){
    return range_max(L, R, 0, 0, N);
  }
};
struct segment_tree_2d{
  int N;
  vector<vector<int>> pos;
  vector<segment_tree> ST;
  segment_tree_2d(int N2){
    N = 1;
    while (N < N2){
      N *= 2;
    }
    pos = vector<vector<int>>(N * 2 - 1);
    ST = vector<segment_tree>(N * 2 - 1);
  }
  void insert(int X, int Y){
    X += N - 1;
    pos[X].push_back(Y);
    while (X > 0){
      X = (X - 1) / 2;
      pos[X].push_back(Y);
    }
  }
  void build(){
    for (int i = 0; i < N * 2 - 1; i++){
      sort(pos[i].begin(), pos[i].end());
      pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
      int cnt = pos[i].size();
      ST[i] = segment_tree(cnt);
    }
  }
  void update(int X, int Y, long long x){
    X += N - 1;
    ST[X].update(lower_bound(pos[X].begin(), pos[X].end(), Y) - pos[X].begin(), x);
    while (X > 0){
      X = (X - 1) / 2;
      ST[X].update(lower_bound(pos[X].begin(), pos[X].end(), Y) - pos[X].begin(), x);
    }
  }
  long long rectangle_max(int L, int R, int U, int D, int i, int l, int r){
    if (r <= L || R <= l){
      return -1;
    } else if (L <= l && r <= R){
      int U2 = lower_bound(pos[i].begin(), pos[i].end(), U) - pos[i].begin();
      int D2 = lower_bound(pos[i].begin(), pos[i].end(), D) - pos[i].begin();
      return ST[i].range_max(U2, D2);
    } else {
      int m = (l + r) / 2;
      return max(rectangle_max(L, R, U, D, i * 2 + 1, l, m), rectangle_max(L, R, U, D, i * 2 + 2, m, r));
    }
  }
  long long rectangle_max(int L, int R, int U, int D){
    return rectangle_max(L, R, U, D, 0, 0, N);
  }
};
int main(){
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n), c(n), d(n), e(n), f(n);
  for (int i = 0; i < n; i++){
    cin >> a[i] >> b[i] >> c[i] >> d[i] >> e[i] >> f[i];
  }
  vector<int> t(q);
  vector<int> a2(q), b2(q), c2(q), d2(q), e2(q), f2(q);
  vector<int> l(q), r(q);
  for (int i = 0; i < q; i++){
    cin >> t[i];
    if (t[i] == 1){
      cin >> a2[i] >> b2[i] >> c2[i] >> d2[i] >> e2[i] >> f2[i];
    }
    if (t[i] == 2){
      cin >> l[i] >> r[i];
    }
  }
  vector<int> x;
  for (int i = 0; i < n; i++){
    x.push_back(min({a[i], c[i], e[i]}));
    x.push_back(max({a[i], c[i], e[i]}));
  }
  for (int i = 0; i < q; i++){
    if (t[i] == 1){
      x.push_back(min({a2[i], c2[i], e2[i]}));
      x.push_back(max({a2[i], c2[i], e2[i]}));
    }
  }
  sort(x.begin(), x.end());
  x.erase(unique(x.begin(), x.end()), x.end());
  int cnt = x.size();
  vector<int> X(n), Y(n);
  for (int i = 0; i < n; i++){
    X[i] = lower_bound(x.begin(), x.end(), min({a[i], c[i], e[i]})) - x.begin();
    Y[i] = lower_bound(x.begin(), x.end(), max({a[i], c[i], e[i]})) - x.begin();
  }
  vector<int> X2(q), Y2(q);
  for (int i = 0; i < q; i++){
    if (t[i] == 1){
      X2[i] = lower_bound(x.begin(), x.end(), min({a2[i], c2[i], e2[i]})) - x.begin();
      Y2[i] = lower_bound(x.begin(), x.end(), max({a2[i], c2[i], e2[i]})) - x.begin();
    }
  }
  segment_tree_2d ST(cnt);
  for (int i = 0; i < n; i++){
    ST.insert(X[i], Y[i]);
  }
  for (int i = 0; i < q; i++){
    if (t[i] == 1){
      ST.insert(X2[i], Y2[i]);
    }
  }
  ST.build();
  for (int i = 0; i < n; i++){
    long long S = abs((long long) (c[i] - a[i]) * (f[i] - b[i]) - (long long) (e[i] - a[i]) * (d[i] - b[i]));
    ST.update(X[i], Y[i], S);
  }
  for (int i = 0; i < q; i++){
    if (t[i] == 1){
      long long S = abs((long long) (c2[i] - a2[i]) * (f2[i] - b2[i]) - (long long) (e2[i] - a2[i]) * (d2[i] - b2[i]));
      ST.update(X2[i], Y2[i], S);
    }
    if (t[i] == 2){
      int l2 = lower_bound(x.begin(), x.end(), l[i]) - x.begin();
      int r2 = upper_bound(x.begin(), x.end(), r[i]) - x.begin();
      cout << ST.rectangle_max(l2, cnt, 0, r2) << endl;
    }
  }
}
0