#725454 (C++14) No.1788 Same Set

• 問題: No.1788 Same Set
• ユーザー: tails
• 提出日時: 2021-12-21 15:04:00
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 204 ms / 4,000 ms
• コード長: 7,140 bytes
• コンパイル時間: 2,390 ms
• コンパイル使用メモリ: 185,732 KB
• 実行使用メモリ: 14,848 KB
• 最終ジャッジ日時: 2024-09-15 15:35:18
• 合計ジャッジ時間: 8,665 ms
• ジャッジサーバーID （参考情報）: judge4 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	3 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	3 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	3 ms; 5,376 KB
testcase_08	AC	3 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	3 ms; 5,376 KB
testcase_11	AC	23 ms; 11,520 KB
testcase_12	AC	93 ms; 11,520 KB
testcase_13	AC	90 ms; 11,392 KB
testcase_14	AC	127 ms; 11,392 KB
testcase_15	AC	150 ms; 11,904 KB
testcase_16	AC	157 ms; 11,904 KB
testcase_17	AC	121 ms; 14,720 KB
testcase_18	AC	147 ms; 12,800 KB
testcase_19	AC	75 ms; 13,312 KB
testcase_20	AC	19 ms; 12,416 KB
testcase_21	AC	152 ms; 12,416 KB
testcase_22	AC	175 ms; 14,592 KB
testcase_23	AC	114 ms; 14,592 KB
testcase_24	AC	137 ms; 14,688 KB
testcase_25	AC	199 ms; 14,688 KB
testcase_26	AC	204 ms; 14,692 KB
testcase_27	AC	20 ms; 14,848 KB
testcase_28	AC	182 ms; 14,820 KB
testcase_29	AC	197 ms; 14,848 KB
testcase_30	AC	19 ms; 14,848 KB
testcase_31	AC	199 ms; 14,720 KB
testcase_32	AC	177 ms; 14,720 KB
testcase_33	AC	176 ms; 14,848 KB
testcase_34	AC	174 ms; 14,692 KB
testcase_35	AC	172 ms; 14,688 KB
testcase_36	AC	169 ms; 14,720 KB
testcase_37	AC	168 ms; 14,848 KB
testcase_38	AC	167 ms; 14,816 KB

ソースコード

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
void*wmem;
char memarr[96000000];
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;
}
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;
  }
}
template<class T> struct segtree_ph{
  int N;
  int logN;
  T*val;
  void malloc(int maxN, int once = 0);
  void walloc(int maxN, int once = 0, void **mem = &wmem);
  void free(void);
  T& operator[](int i);
  void setN(int n, int zerofill = 1, int dobuild = 1);
  void build(void);
  inline void build(int a);
  inline void change(int a, T v);
  inline void changed(int a);
  inline T get(int a, int b);
}
;
struct segt{
  int c;
  int d;
  int e;
}
;
inline segt segtree_ph_func(segt a,segt b){
  segt r;
  int de=a.d-b.e;
  r.d=(de>=0?de:0)+b.d;
  r.e=(de>=0?0:-de)+a.e;
  r.c=(de>=0?a.c:0)+(de<=0?b.c:0);
  return r;
}
int pa[400000+1];
int pb[400000+1];
int main(){
  int i;
  wmem = memarr;
  int n;
  rd(n);
  int a[n];
  {
    int Nzj9Y0kE;
    for(Nzj9Y0kE=(0);Nzj9Y0kE<(n);Nzj9Y0kE++){
      rd(a[Nzj9Y0kE]);
    }
  }
  int b[n];
  {
    int QAAnbtfa;
    for(QAAnbtfa=(0);QAAnbtfa<(n);QAAnbtfa++){
      rd(b[QAAnbtfa]);
    }
  }
  segtree_ph<segt> t;
  t.walloc(n+3,1);
  t[0]=t[n+2]=segt{0,0,0};
  {
    int R5MtCiij;
    for(R5MtCiij=(1);R5MtCiij<((n+1) + 1);R5MtCiij++){
      t[R5MtCiij]=segt{1,0,0};
    }
  }
  t.build();
  long z=0;
  for(i=(0);i<(n);i++){
    int ai=a[i];
    int bi=b[i];
    if(pa[ai]<pb[ai]){
      {
        int j=pa[ai];
        t[j+0].d-=1;
        t.changed(j+0);
      }
      {
        int j=pb[ai];
        t[j+1].e-=1;
        t.changed(j+1);
      }
    }
    else if(pb[ai]<pa[ai]){
      {
        int j=pb[ai];
        t[j+0].d-=1;
        t.changed(j+0);
      }
      {
        int j=pa[ai];
        t[j+1].e-=1;
        t.changed(j+1);
      }
    }
    if(ai!=bi){
      if(pa[bi]<pb[bi]){
        {
          int j=pa[bi];
          t[j+0].d-=1;
          t.changed(j+0);
        }
        {
          int j=pb[bi];
          t[j+1].e-=1;
          t.changed(j+1);
        }
      }
      else if(pb[bi]<pa[bi]){
        {
          int j=pb[bi];
          t[j+0].d-=1;
          t.changed(j+0);
        }
        {
          int j=pa[bi];
          t[j+1].e-=1;
          t.changed(j+1);
        }
      }
      {
        int j=pb[ai];
        t[j+0].d+=1;
        t.changed(j+0);
      }
      {
        int j=pa[bi];
        t[j+0].d+=1;
        t.changed(j+0);
      }
      {
        int j=i+1;
        t[j+1].e+=2;
        t.changed(j+1);
      }
    }
    pa[ai]=i+1;
    pb[bi]=i+1;
    z+=t.val[1].c+i-n;
  }
  dprintf(1,"%ld\n",z);
  return 0;
}
template<class T> void segtree_ph<T>::malloc(int maxN, int once /*= 0*/){
  int i;
  for(i=1;i<maxN;i*=2){
    ;
  }
  val = new T[2*i];
  if(once){
    setN(maxN);
  }
}
template<class T> void segtree_ph<T>::walloc(int maxN, int once /*= 0*/, void **mem /*= &wmem*/){
  int i;
  for(i=1;i<maxN;i*=2){
    ;
  }
  walloc1d(&val, 2*i, mem);
  if(once){
    setN(maxN);
  }
}
template<class T> void segtree_ph<T>::free(void){
  delete [] val;
}
template<class T> T& segtree_ph<T>::operator[](int i){
  return val[N+i];
}
template<class T> void segtree_ph<T>::setN(int n, int zerofill /*= 1*/, int dobuild /*= 1*/){
  int i;
  for(i=1,logN=0;i<n;i*=2,logN++){
    ;
  }
  N = i;
  if(dobuild){
    build();
  }
}
template<class T> void segtree_ph<T>::build(void){
  for(int i=N-1;i;i--){
    val[i] = segtree_ph_func(val[2*i], val[2*i+1]);
  }
}
template<class T> inline void segtree_ph<T>::build(int a){
  while(a > 1){
    a /= 2;
    val[a] = segtree_ph_func(val[2*a], val[2*a+1]);
  }
}
template<class T> inline void segtree_ph<T>::change(int a, T v){
  val[a+N] = v;
  build(a+N);
}
template<class T> inline void segtree_ph<T>::changed(int a){
  build(a+N);
}
template<class T> inline T segtree_ph<T>::get(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 = segtree_ph_func(res, val[a]);
      }
      else{
        res = val[a];
        fga = 1;
      }
      a++;
    }
    if(b%2){
      b--;
      if(fgb){
        tmp = segtree_ph_func(val[b], tmp);
      }
      else{
        tmp = val[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){
    return segtree_ph_func(res, tmp);
  }
  return res;
}
// modified
// cLay version 20211024-1

// --- original code ---
// struct segt{
// 	int c;
// 	int d,e;
// };
// 
// inline
// segt segtree_ph_func(segt a,segt b){
// 	segt r;
// 	int de=a.d-b.e;
// 	r.d=(de>=0?de:0)+b.d;
// 	r.e=(de>=0?0:-de)+a.e;
// 	r.c=(de>=0?a.c:0)+(de<=0?b.c:0);
// 	return r;
// }
// 
// int pa[4d5+1],pb[4d5+1];
// 
// {
// 	int@n,@a[n],@b[n];
// 	
// 	segtree_ph<segt> t;
// 	t.walloc(n+3,1);
// //	t[0..n+2]=segt{0,0,0};
// 	t[0]=t[n+2]=segt{0,0,0};
// 	t[1..n+1]=segt{1,0,0};
// 	t.build();
// 	long z=0;
// 	rep(i,n){
// 		int ai=a[i];
// 		int bi=b[i];
// 		if(pa[ai]<pb[ai]){
// 			{
// 				int j=pa[ai];
// 				t[j+0].d-=1;
// 				t.changed(j+0);
// 			}
// 			{
// 				int j=pb[ai];
// 				t[j+1].e-=1;
// 				t.changed(j+1);
// 			}
// 		}else if(pb[ai]<pa[ai]){
// 			{
// 				int j=pb[ai];
// 				t[j+0].d-=1;
// 				t.changed(j+0);
// 			}
// 			{
// 				int j=pa[ai];
// 				t[j+1].e-=1;
// 				t.changed(j+1);
// 			}
// 		}
// 		if(ai!=bi){
// 			if(pa[bi]<pb[bi]){
// 				{
// 					int j=pa[bi];
// 					t[j+0].d-=1;
// 					t.changed(j+0);
// 				}
// 				{
// 					int j=pb[bi];
// 					t[j+1].e-=1;
// 					t.changed(j+1);
// 				}
// 			}else if(pb[bi]<pa[bi]){
// 				{
// 					int j=pb[bi];
// 					t[j+0].d-=1;
// 					t.changed(j+0);
// 				}
// 				{
// 					int j=pa[bi];
// 					t[j+1].e-=1;
// 					t.changed(j+1);
// 				}
// 			}
// 			{
// 				int j=pb[ai];
// 				t[j+0].d+=1;
// 				t.changed(j+0);
// 			}
// 			{
// 				int j=pa[bi];
// 				t[j+0].d+=1;
// 				t.changed(j+0);
// 			}
// 			{
// 				int j=i+1;
// 				t[j+1].e+=2;
// 				t.changed(j+1);
// 			}
// 		}
// 		pa[ai]=i+1;
// 		pb[bi]=i+1;
// 		z+=t.val[1].c+i-n;
// 	}
// 	dprintf(1,"%ld\n",z);
// }