#682966 (C++17) No.1625 三角形の質問

提出ソース

結果

問題	No.1625 三角形の質問
ユーザー	LayCurse
提出日時	2021-07-23 23:28:40
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	13,058 bytes
コンパイル時間	3,254 ms
コンパイル使用メモリ	244,580 KB
実行使用メモリ	43,512 KB
最終ジャッジ日時	2024-07-18 21:27:07
合計ジャッジ時間	18,549 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	47 ms 6,400 KB
testcase_02	AC	1,890 ms 13,312 KB
testcase_03	AC	496 ms 14,848 KB
testcase_04	AC	923 ms 11,648 KB
testcase_05	AC	3,025 ms 18,304 KB
testcase_06	TLE	-
testcase_07	--	-
testcase_08	--	-
testcase_09	--	-
testcase_10	--	-
testcase_11	--	-
testcase_12	--	-
testcase_13	--	-
testcase_14	--	-
testcase_15	--	-
testcase_16	--	-
testcase_17	--	-
testcase_18	--	-
testcase_19	--	-

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

コンパイルメッセージ

main.cpp: In function 'void solve(int, int*, int*, long long int*, int, int*, int*, long long int*, void*)':
main.cpp:431:18: warning: 'res' may be used uninitialized [-Wmaybe-uninitialized]
  431 |     res[qind[i]] = t.getMaxVal(0, qy[i]+1);
      |     ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:300:7: note: 'res' was declared here
  300 |     T res;
      |       ^~~
main.cpp:301:7: warning: 'tmp' may be used uninitialized [-Wmaybe-uninitialized]
  301 |     T tmp;
      |       ^~~

ソースコード

raw source code

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
template<class T> struct cLtraits_identity{
  using type = T;
}
;
template<class T> using cLtraits_try_make_signed =
  typename conditional<
    is_integral<T>::value,
    make_signed<T>,
    cLtraits_identity<T>
    >::type;
template <class S, class T> struct cLtraits_common_type{
  using tS = typename cLtraits_try_make_signed<S>::type;
  using tT = typename cLtraits_try_make_signed<T>::type;
  using type = typename common_type<tS,tT>::type;
}
;
void*wmem;
char memarr[96000000];
template<class S, class T> inline auto min_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a <= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class S, class T> inline auto max_L(S a, T b)
-> typename cLtraits_common_type<S,T>::type{
  return (typename cLtraits_common_type<S,T>::type) a >= (typename cLtraits_common_type<S,T>::type) b ? a : b;
}
template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  (*arr)=(T*)(*mem);
  (*mem)=((*arr)+x);
}
template<class T> inline void walloc1d(T **arr, int x1, int x2, void **mem = &wmem){
  walloc1d(arr, x2-x1, mem);
  (*arr) -= x1;
}
template<class T1, class T2, class T3> void sortA_L(int N, T1 a[], T2 b[], T3 c[], void *mem = wmem){
  int i;
  pair<T1, pair<T2, T3> >*arr;
  walloc1d(&arr, N, &mem);
  for(i=(0);i<(N);i++){
    arr[i].first = a[i];
    arr[i].second.first = b[i];
    arr[i].second.second = c[i];
  }
  sort(arr, arr+N);
  for(i=(0);i<(N);i++){
    a[i] = arr[i].first;
    b[i] = arr[i].second.first;
    c[i] = arr[i].second.second;
  }
}
template<class T1, class T2, class T3, class T4> void sortA_L(int N, T1 a[], T2 b[], T3 c[], T4 d[], void *mem = wmem){
  int i;
  pair<pair<T1, T2>, pair<T3, T4> >*arr;
  walloc1d(&arr, N, &mem);
  for(i=(0);i<(N);i++){
    arr[i].first.first = a[i];
    arr[i].first.second = b[i];
    arr[i].second.first = c[i];
    arr[i].second.second = d[i];
  }
  sort(arr, arr+N);
  for(i=(0);i<(N);i++){
    a[i] = arr[i].first.first;
    b[i] = arr[i].first.second;
    c[i] = arr[i].second.first;
    d[i] = arr[i].second.second;
  }
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(long long x){
  int s=0;
  int m=0;
  char f[20];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
template<class T> int coordcomp_L(int n, T arr[], int res[] = NULL, void *mem = wmem){
  int i;
  int k = 0;
  pair<T,int>*r;
  walloc1d(&r, n, &mem);
  for(i=(0);i<(n);i++){
    r[i].first = arr[i];
    r[i].second = i;
  }
  sort(r, r+n);
  if(res != NULL){
    for(i=(0);i<(n);i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      res[r[i].second] = k;
    }
  }
  else{
    for(i=(0);i<(n);i++){
      if(i && r[i].first != r[i-1].first){
        k++;
      }
      arr[r[i].second] = k;
    }
  }
  return k+1;
}
template<class T> int coordcomp_L(int n1, T arr1[], int n2, T arr2[], int res1[] = NULL, int res2[] = NULL, void *mem = wmem){
  int i;
  int k = 0;
  pair<T,int>*r;
  walloc1d(&r, n1+n2, &mem);
  for(i=(0);i<(n1);i++){
    r[i].first = arr1[i];
    r[i].second = i;
  }
  for(i=(0);i<(n2);i++){
    r[n1+i].first = arr2[i];
    r[n1+i].second = n1+i;
  }
  sort(r, r+n1+n2);
  for(i=(0);i<(n1+n2);i++){
    if(i && r[i].first != r[i-1].first){
      k++;
    }
    if(r[i].second < n1){
      if(res1!=NULL){
        res1[r[i].second] = k;
      }
      else{
        arr1[r[i].second] = k;
      }
    }
    else{
      if(res2!=NULL){
        res2[r[i].second-n1] = k;
      }
      else{
        arr2[r[i].second-n1] = k;
      }
    }
  }
  return k+1;
}
template<class T> struct segtree_Point_Maxval{
  int N;
  int logN;
  T*mx;
  void malloc(int maxN, int once = 0){
    int i;
    for(i=1;i<maxN;i*=2){
      ;
    }
    mx = new T[2*i];
    if(once){
      setN(maxN);
    }
  }
  void walloc(int maxN, int once = 0, void **mem = &wmem){
    int i;
    for(i=1;i<maxN;i*=2){
      ;
    }
    walloc1d(&mx, 2*i, mem);
    if(once){
      setN(maxN);
    }
  }
  void free(void){
    delete [] mx;
  }
  T& operator[](int i){
    return mx[N+i];
  }
  void setN(int n, int zerofill = 1, int dobuild = 1){
    int i;
    for(i=1,logN=0;i<n;i*=2,logN++){
      ;
    }
    N = i;
    if(zerofill){
      for(i=(0);i<(N);i++){
        mx[N+i] = 0;
      }
    }
    if(dobuild){
      build();
    }
  }
  void build(void){
    int i;
    for(i=N-1;i;i--){
      mx[i] =max_L(mx[2*i], mx[2*i+1]);
    }
  }
  inline void build(int a){
    while(a > 1){
      a /= 2;
      mx[a] =max_L(mx[2*a], mx[2*a+1]);
    }
  }
  inline void change(int a, T val){
    mx[a+N] = val;
    build(a+N);
  }
  inline void add(int a, T val){
    mx[a+N] += val;
    build(a+N);
  }
  inline T getMaxVal(int a, int b){
    T res;
    T tmp;
    int fga = 0;
    int fgb = 0;
    a += N;
    b += N;
    while(a < b){
      if(a%2){
        if(fga){
          res =max_L(res, mx[a]);
        }
        else{
          res = mx[a];
          fga = 1;
        }
        a++;
      }
      if(b%2){
        b--;
        if(fgb){
          tmp =max_L(mx[b], tmp);
        }
        else{
          tmp = mx[b];
          fgb = 1;
        }
      }
      a /= 2;
      b /= 2;
    }
    if(fga==1 && fgb==0){
      return res;
    }
    if(fga==0 && fgb==1){
      return tmp;
    }
    if(fga==1 && fgb==1){
      res =max_L(res, tmp);
      return res;
    }
    return res;
  }
}
;
long long crossProd_L(long long x1, long long y1, long long x2, long long y2){
  return x1 * y2 - x2 * y1;
}
int N;
int Q;
int T[200000];
int A[200000];
int B[200000];
int C[200000];
int D[200000];
int E[200000];
int F[200000];
int L[200000];
int R[200000];
int ind[200000];
int x[200000];
int y[200000];
long long s[200000];
int qx[200000];
int qy[200000];
void solve(int n, int x[], int y[], long long s[], int q, int x1[], int y1[], long long res[], void *mem = wmem){
  int i;
  int xs;
  int*larr;
  int*nx;
  int*ny;
  int*qx;
  int*qy;
  int*nind;
  int*qind;
  long long*sarr;
  segtree_Point_Maxval<long long> t;
  walloc1d(&larr, 2*n+2*q, &mem);
  walloc1d(&nx, n, &mem);
  walloc1d(&ny, n, &mem);
  walloc1d(&qx, q, &mem);
  walloc1d(&qy, q, &mem);
  walloc1d(&nind, n, &mem);
  walloc1d(&qind, q, &mem);
  for(i=(0);i<(n);i++){
    larr[i] = x[i];
  }
  for(i=(0);i<(n);i++){
    larr[n+i] = y[i];
  }
  for(i=(0);i<(q);i++){
    larr[n+n+i] = x1[i];
  }
  for(i=(0);i<(q);i++){
    larr[n+n+q+i] = y1[i];
  }
  xs =coordcomp_L(2*n+2*q,larr,NULL,mem);
  for(i=(0);i<(n);i++){
    nx[i] = larr[i];
  }
  for(i=(0);i<(n);i++){
    ny[i] = larr[n+i];
  }
  for(i=(0);i<(q);i++){
    qx[i] = larr[n+n+i];
  }
  for(i=(0);i<(q);i++){
    qy[i] = larr[n+n+q+i];
  }
  for(i=(0);i<(n);i++){
    nind[i] = i;
  }
  for(i=(0);i<(q);i++){
    qind[i] = i;
  }
  sortA_L(n, nx, ny, nind, mem);
  sortA_L(q, qx, qy, qind, mem);
  walloc1d(&sarr, xs, &mem);
  t.walloc(xs, 0, &mem);
  t.setN(xs);
  for(i=(0);i<(xs);i++){
    t[i] = sarr[i] = -1;
  }
  t.build();
  for(i=(q)-1;i>=(0);i--){
    while(n && nx[n-1] >= qx[i]){
      if(sarr[ny[n-1]] < s[nind[n-1]]){
        sarr[ny[n-1]] = s[nind[n-1]];
        t.change(ny[n-1], sarr[ny[n-1]]);
      }
      n--;
    }
    res[qind[i]] = t.getMaxVal(0, qy[i]+1);
  }
}
long long res[200000];
long long tmp[200000];
int main(){
  wmem = memarr;
  int i;
  int j;
  int k;
  int nst;
  int ned;
  int nn;
  int qst;
  int qed;
  rd(N);
  rd(Q);
  {
    int Q5rsz4fz;
    for(Q5rsz4fz=(0);Q5rsz4fz<(N);Q5rsz4fz++){
      rd(A[Q5rsz4fz]);
      rd(B[Q5rsz4fz]);
      rd(C[Q5rsz4fz]);
      rd(D[Q5rsz4fz]);
      rd(E[Q5rsz4fz]);
      rd(F[Q5rsz4fz]);
    }
  }
  nn = N;
  for(i=(0);i<(Q);i++){
    rd(T[i]);
    if(T[i]==1){
      rd(A[nn]);
      rd(B[nn]);
      rd(C[nn]);
      rd(D[nn]);
      rd(E[nn]);
      rd(F[nn]);
      ind[i] = nn++;
    }
    if(T[i]==2){
      rd(L[i]);
      rd(R[i]);
    }
  }
  for(i=(0);i<(nn);i++){
    x[i] =min_L(min_L(A[i], C[i]), E[i]);
    y[i] =max_L(max_L(A[i], C[i]), E[i]);
    s[i] = abs(crossProd_L(C[i]-A[i], D[i]-B[i], E[i]-A[i], F[i]-B[i]));
  }
  nst = ned = N;
  qst = qed = 0;
  for(i=(0);i<(Q);i++){
    if(T[i]==1){
      ned++;
    }
    else{
      res[qed] = -1;
      for(k=(nst);k<(ned);k++){
        if(L[i]<=x[k]&&y[k]<=R[i]){
          chmax(res[qed], s[k]);
        }
      }
      qx[qed] = L[i];
      qy[qed] = R[i];
      qed++;
    }
    if(nst + 200 < ned){
      if(qst < qed){
        solve(nst, x, y, s, qed-qst, qx+qst, qy+qst, tmp+qst);
        while(qst < qed){
          chmax(res[qst], tmp[qst]);
          qst++;
        }
      }
      nst = ned;
    }
  }
  if(qst < qed){
    solve(nst, x, y, s, qed-qst, qx+qst, qy+qst, tmp+qst);
    while(qst < qed){
      chmax(res[qst], tmp[qst]);
      qst++;
    }
  }
  for(i=(0);i<(qed);i++){
    wt_L(res[i]);
    wt_L('\n');
  }
  return 0;
}
// cLay version 20210717-1 [beta]

// --- original code ---
// int N, Q, T[2d5], A[], B[], C[], D[], E[], F[], L[], R[], ind[];
// int x[], y[]; ll s[];
// int qx[], qy[];
// 
// void solve(int n, int x[], int y[], ll s[], int q, int x1[], int y1[], ll res[], void *mem = wmem){
//   int i, xs;
//   int *larr;
//   int *nx, *ny, *qx, *qy, *nind, *qind;
//   ll *sarr;
//   segtree_Point_Maxval<ll> t;
//   walloc1d(&larr, 2*n+2*q, &mem);
//   walloc1d(&nx, n, &mem);
//   walloc1d(&ny, n, &mem);
//   walloc1d(&qx, q, &mem);
//   walloc1d(&qy, q, &mem);
//   walloc1d(&nind, n, &mem);
//   walloc1d(&qind, q, &mem);
// 
//   rep(i,n) larr[i] = x[i];
//   rep(i,n) larr[n+i] = y[i];
//   rep(i,q) larr[n+n+i] = x1[i];
//   rep(i,q) larr[n+n+q+i] = y1[i];
//   xs = coordcomp(2*n+2*q,larr,NULL,mem);
//   rep(i,n) nx[i] = larr[i];
//   rep(i,n) ny[i] = larr[n+i];
//   rep(i,q) qx[i] = larr[n+n+i];
//   rep(i,q) qy[i] = larr[n+n+q+i];
// 
//   rep(i,n) nind[i] = i;
//   rep(i,q) qind[i] = i;
// 
//   sortA(n, nx, ny, nind, mem);
//   sortA(q, qx, qy, qind, mem);
// 
//   walloc1d(&sarr, xs, &mem);
// 
//   t.walloc(xs, 0, &mem);
//   t.setN(xs);
//   rep(i,xs) t[i] = sarr[i] = -1;
//   t.build();
// 
//   rrep(i,q){
//     while(n && nx[n-1] >= qx[i]){
//       if(sarr[ny[n-1]] < s[nind[n-1]]){
//         sarr[ny[n-1]] = s[nind[n-1]];
//         t.change(ny[n-1], sarr[ny[n-1]]);
//       }
//       n--;
//     }
//     res[qind[i]] = t.getMaxVal(0, qy[i]+1);
//   }
// }
// 
// ll res[], tmp[];
// {
//   int i, j, k, nst, ned, nn, qst, qed;
//   rd(N,Q,(A,B,C,D,E,F)(N));
//   nn = N;
//   rep(i,Q){
//     rd(T[i]);
//     if(T[i]==1) rd(A[nn], B[nn], C[nn], D[nn], E[nn], F[nn]), ind[i] = nn++;
//     if(T[i]==2) rd(L[i], R[i]);
//   }
//   rep(i,nn){
//     x[i] = min(A[i], C[i], E[i]);
//     y[i] = max(A[i], C[i], E[i]);
//     s[i] = abs(crossProd(C[i]-A[i], D[i]-B[i], E[i]-A[i], F[i]-B[i]));
//   }
//   nst = ned = N;
//   qst = qed = 0;
//   rep(i,Q){
//     if(T[i]==1){
//       ned++;
//     } else {
//       res[qed] = -1;
//       rep(k,nst,ned) if(L[i]<=x[k]&&y[k]<=R[i]) res[qed] >?= s[k];
//       qx[qed] = L[i];
//       qy[qed] = R[i];
//       qed++;
//     }
//     if(nst + 200 < ned){
//       if(qst < qed){
//         solve(nst, x, y, s, qed-qst, qx+qst, qy+qst, tmp+qst);
//         while(qst < qed){
//           res[qst] >?= tmp[qst];
//           qst++;
//         }
//       }
//       nst = ned;
//     }
//   }
//   if(qst < qed){
//     solve(nst, x, y, s, qed-qst, qx+qst, qy+qst, tmp+qst);
//     while(qst < qed){
//       res[qst] >?= tmp[qst];
//       qst++;
//     }
//   }
//   rep(i,qed) wt(res[i]);
// }

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード