結果

問題 No.1625 三角形の質問
コンテスト
ユーザー tails
提出日時 2021-08-12 17:35:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 527 ms / 6,000 ms
コード長 13,443 bytes
コンパイル時間 2,676 ms
コンパイル使用メモリ 197,420 KB
実行使用メモリ 77,824 KB
最終ジャッジ日時 2024-10-01 22:20:11
合計ジャッジ時間 13,867 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 T> void malloc1d(T **arr, int x){
  (*arr) = (T*)malloc(x*sizeof(T));
}
template<class T> void free1d(T *arr){
  free(arr);
}
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;
  }
}
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(long long &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(int x){
  int s=0;
  int m=0;
  char f[10];
  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');
  }
}
inline void wt_L(unsigned x){
  int s=0;
  char f[10];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
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');
  }
}
inline void wt_L(unsigned long long x){
  int s=0;
  char f[21];
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
int WRITER_DOUBLE_DIGIT = 15;
inline int writerDigit_double(){
  return WRITER_DOUBLE_DIGIT;
}
inline void writerDigit_double(int d){
  WRITER_DOUBLE_DIGIT = d;
}
inline void wt_L(double x){
  const int d = WRITER_DOUBLE_DIGIT;
  int k;
  int r;
  double v;
  if(x!=x || (x==x+1 && x==2*x)){
    my_putchar_unlocked('E');
    my_putchar_unlocked('r');
    my_putchar_unlocked('r');
    return;
  }
  if(x < 0){
    my_putchar_unlocked('-');
    x = -x;
  }
  x += 0.5 * pow(0.1, d);
  r = 0;
  v = 1;
  while(x >= 10*v){
    v *= 10;
    r++;
  }
  while(r >= 0){
    r--;
    k = floor(x / v);
    if(k >= 10){
      k = 9;
    }
    if(k <= -1){
      k = 0;
    }
    x -= k * v;
    v *= 0.1;
    my_putchar_unlocked(k + '0');
  }
  if(d > 0){
    my_putchar_unlocked('.');
    v = 1;
    for(r=(0);r<(d);r++){
      v *= 0.1;
      k = floor(x / v);
      if(k >= 10){
        k = 9;
      }
      if(k <= -1){
        k = 0;
      }
      x -= k * v;
      my_putchar_unlocked(k + '0');
    }
  }
}
inline void wt_L(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
inline void wt_L(string &x){
  int i=0;
  for(i=0;x[i]!='\0';i++){
    my_putchar_unlocked(x[i]);
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
template<class T> struct fenwick{
  int size;
  int memory;
  T*data;
  void malloc(int mem);
  void malloc(int mem, int fg);
  void walloc(int mem, void **workMemory = &wmem);
  void walloc(int mem, int fg, void **workMemory = &wmem);
  void free(void);
  void init(int N);
  void add(int k, T val);
  T get(int k);
  T range(int a, int b);
  int kth(T k);
}
;
template<class S, class T1, class T2> struct rangeTree2d{
  int N;
  int N2;
  int*sz;
  S*tot;
  fenwick<S>*w;
  T1**d1;
  T1*ddd1;
  T2*d2;
  inline void build(int nn, T1 dd1[], T2 dd2[], S ww[] = NULL, void **mem = &wmem){
    int i;
    int j;
    int i1;
    int i2;
    int k1;
    int k2;
    int s;
    int s1;
    int s2;
    S*www;
    N = nn;
    for(N2=1;N2<N;N2*=2){
      ;
    }
    walloc1d(&sz,2*N2,mem);
    walloc1d(&tot,2*N2,mem);
    walloc1d(&w,2*N2,mem);
    walloc1d(&d1,2*N2,mem);
    walloc1d(&d2,nn,mem);
    malloc1d(&www,nn);
    walloc1d(&ddd1,nn);
    if(ww==NULL){
      for(i=(0);i<(N);i++){
        www[i] = 1;
      }
    }
    else{
      for(i=(0);i<(N);i++){
        www[i] = ww[i];
      }
    }
    for(i=(0);i<(N);i++){
      ddd1[i] = dd1[i];
    }
    for(i=(0);i<(N);i++){
      d2[i] = dd2[i];
    }
    sortA_L(N,d2,ddd1,www);
    for(i=(0);i<(N);i++){
      sz[N2+i] = 1;
      walloc1d(&d1[N2+i], 1, mem);
      d1[N2+i][0] = ddd1[i];
      w[N2+i].walloc(1, mem);
      w[N2+i].init(1);
      w[N2+i].add(0,www[i]);
      tot[N2+i] = www[i];
    }
    for(i=(N);i<(N2);i++){
      sz[N2+i] = 0;
      tot[N2+i] = 0;
    }
    for(i=(N2)-1;i>=(1);i--){
      i1 = 2*i;
      i2 = 2*i + 1;
      s1 = sz[i1];
      s2 = sz[i2];
      sz[i] = s1 + s2;
      s = k1 = k2 = 0;
      walloc1d(&d1[i], sz[i], mem);
      w[i].walloc(sz[i], mem);
      w[i].init(sz[i]);
      while(k1 < s1 || k2 < s2){
        if(k2==s2){
          d1[i][s] = d1[i1][k1];
          w[i].add(s,w[i1].range(k1,k1));
          s++;
          k1++;
          continue;
        }
        if(k1==s1){
          d1[i][s] = d1[i2][k2];
          w[i].add(s,w[i2].range(k2,k2));
          s++;
          k2++;
          continue;
        }
        if(d1[i1][k1] < d1[i2][k2]){
          d1[i][s] = d1[i1][k1];
          w[i].add(s,w[i1].range(k1,k1));
          s++;
          k1++;
          continue;
        }
        else{
          d1[i][s] = d1[i2][k2];
          w[i].add(s,w[i2].range(k2,k2));
          s++;
          k2++;
          continue;
        }
      }
    }
    free1d(www);
  }
  inline void /* int */ add(T1 x, T2 y, S v){
    int a;
    int b;
    int z;
    a = lower_bound(d2, d2+N, y) - d2;
    b = upper_bound(d2, d2+N, y) - d2;
    z = lower_bound(ddd1+a, ddd1+b, x) - ddd1 + N2;
    while(z){
      a = lower_bound(d1[z], d1[z]+sz[z], x) - d1[z];
      w[z].add(a, v);
      z /= 2;
    }
  }
  inline S query(T1 x1, T1 x2, T2 y1, T2 y2){
    S res = 0;
    int a;
    int b;
    int z1;
    int z2;
    a = lower_bound(d2, d2+N, y1) - d2 + N2;
    b = lower_bound(d2, d2+N, y2) - d2 + N2;
    while(a < b){
      if(a%2){
        z1 = lower_bound(d1[a], d1[a]+sz[a], x1) - d1[a];
        z2 = lower_bound(d1[a], d1[a]+sz[a], x2) - d1[a];
        if(z1 < z2){
          res += w[a].range(z1,z2-1);
        }
        a++;
      }
      if(b%2){
        b--;
        z1 = lower_bound(d1[b], d1[b]+sz[b], x1) - d1[b];
        z2 = lower_bound(d1[b], d1[b]+sz[b], x2) - d1[b];
        if(z1 < z2){
          res += w[b].range(z1,z2-1);
        }
      }
      a /= 2;
      b /= 2;
    }
    return res;
  }
}
;
struct T{
  long long v;
  T(){
  }
  T(long long i){
    v=i;
  }
  void operator=(long long i){
    v=i;
  }
  void operator+=(T a){
    chmax(v, a.v);
  }
}
;
T operator-(T a,T b){
  return a;
}
bool operator<(T a,T b){
  return a.v<b.v;
}
rangeTree2d<T,int,int> t;
int dd1[200000];
int dd2[200000];
T ww[200000];
struct Q{
  int t;
  long long l;
  long long r;
  long long s;
}
;
Q qs[100000];
long long area(long long a,long long b,long long c,long long d,long long e,long long f){
  return abs((c-a)*(f-b)-(d-b)*(e-a));
}
int l_offs=1073709056;
int main(){
  int i;
  wmem = memarr;
  long long n;
  rd(n);
  long long q;
  rd(q);
  for(i=(0);i<(n);i++){
    long long a;
    rd(a);
    long long b;
    rd(b);
    long long c;
    rd(c);
    long long d;
    rd(d);
    long long e;
    rd(e);
    long long f;
    rd(f);
    long long l=min_L(min_L(a, c), e);
    long long r=max_L(max_L(a, c), e);
    long long s=area(a,b,c,d,e,f);
    dd1[i]=l_offs-l;
    dd2[i]=r;
    ww[i].v=s;
  }
  long long m=n;
  for(i=(0);i<(q);i++){
    long long t;
    rd(t);
    qs[i].t=t;
    if(t&1){
      long long a;
      rd(a);
      long long b;
      rd(b);
      long long c;
      rd(c);
      long long d;
      rd(d);
      long long e;
      rd(e);
      long long f;
      rd(f);
      long long l=min_L(min_L(a, c), e);
      long long r=max_L(max_L(a, c), e);
      long long s=area(a,b,c,d,e,f);
      dd1[m]=l_offs-l;
      dd2[m]=r;
      ww[m].v=0;
      ++m;
      qs[i].l=l;
      qs[i].r=r;
      qs[i].s=s;
    }
    else{
      long long l;
      rd(l);
      long long r;
      rd(r);
      qs[i].l=l;
      qs[i].r=r;
    }
  }
  t.build(m,dd1,dd2,ww);
  for(i=(0);i<(q);i++){
    if(qs[i].t&1){
      t.add(l_offs-qs[i].l,qs[i].r,qs[i].s);
    }
    else{
      wt_L(t.query(0,l_offs-qs[i].l+1,0,qs[i].r+1).v?:-1);
      wt_L('\n');
    }
  }
  return 0;
}
template<class T> void fenwick<T>::malloc(int mem){
  memory = mem;
  data = (T*)std::malloc(sizeof(T)*mem);
}
template<class T> void fenwick<T>::malloc(int mem, int fg){
  memory = mem;
  data = (T*)std::malloc(sizeof(T)*mem);
  if(fg){
    init(mem);
  }
}
template<class T> void fenwick<T>::walloc(int mem, void **workMemory /* = &wmem*/){
  memory = mem;
  walloc1d(&data, mem, workMemory);
}
template<class T> void fenwick<T>::walloc(int mem, int fg, void **workMemory /* = &wmem*/){
  memory = mem;
  walloc1d(&data, mem, workMemory);
  if(fg){
    init(mem);
  }
}
template<class T> void fenwick<T>::free(void){
  memory = 0;
  free(data);
}
template<class T> void fenwick<T>::init(int N){
  size = N;
  memset(data,0,sizeof(T)*N);
}
template<class T> void fenwick<T>::add(int k, T val){
  while(k < size){
    data[k] += val;
    k |= k+1;
  }
}
template<class T> T fenwick<T>::get(int k){
  T res = 0;
  while(k>=0){
    res += data[k];
    k = (k&(k+1))-1;
  }
  return res;
}
template<class T> T fenwick<T>::range(int a, int b){
  if(a < 0){
    a = 0;
  }
  if(b >= size){
    b = size - 1;
  }
  if(b < a){
    return 0;
  }
  return get(b) - get(a-1);
}
template<class T> int fenwick<T>::kth(T k){
  int i=0;
  int j=size;
  int c;
  T v;
  while(i<j){
    c = (i+j)/2;
    v = get(c);
    if(v <= k){
      i=c+1;
    }
    else{
      j=c;
    }
  }
  return i==size?-1:i;
}
// cLay version 20210708-1

// --- original code ---
// struct T {
// 	ll v;
// 	T(){
// 	}
// 	T(ll i){
// 		v=i;
// 	}
// 	void operator=(ll i){
// 		v=i;
// 	}
// 	void operator+=(T a){
// 		v>?=a.v;
// 	}
// };
// 
// T operator-(T a,T b){
// 	return a;
// }
// 
// bool operator<(T a,T b){
// 	return a.v<b.v;
// }
// 
// rangeTree2d<T,int,int>t;
// 
// int dd1[2d5],dd2[];
// T ww[];
// 
// struct Q {
// 	int t;
// 	ll l,r,s;
// };
// Q qs[1d5];
// 
// ll area(ll a,ll b,ll c,ll d,ll e,ll f){
// 	return abs((c-a)*(f-b)-(d-b)*(e-a));
// }
// 
// int l_offs=int_inf;
// 
// {
// 	ll@n,@q;
// 	rep(i,n){
// 		ll@a,@b,@c,@d,@e,@f;
// 		ll l=min(a,c,e);
// 		ll r=max(a,c,e);
// 		ll s=area(a,b,c,d,e,f);
// 		dd1[i]=l_offs-l;
// 		dd2[i]=r;
// 		ww[i].v=s;
// 	}
// 	ll m=n;
// 	rep(i,q){
// 		ll@t;
// 		qs[i].t=t;
// 		if(t&1){
// 			ll@a,@b,@c,@d,@e,@f;
// 			ll l=min(a,c,e);
// 			ll r=max(a,c,e);
// 			ll s=area(a,b,c,d,e,f);
// 			dd1[m]=l_offs-l;
// 			dd2[m]=r;
// 			ww[m].v=0;
// 			++m;
// 			qs[i].l=l;
// 			qs[i].r=r;
// 			qs[i].s=s;
// 		}else{
// 			ll@l,@r;
// 			qs[i].l=l;
// 			qs[i].r=r;
// 		}
// 	}
// 	t.build(m,dd1,dd2,ww);
// 	rep(i,q){
// 		if(qs[i].t&1){
// 			t.add(l_offs-qs[i].l,qs[i].r,qs[i].s);
// 		}else{
// 			wt(t.query(0,l_offs-qs[i].l+1,0,qs[i].r+1).v?:-1);
// 		}
// 	}
// }
0