結果

問題 No.1788 Same Set
ユーザー tailstails
提出日時 2021-12-21 15:04:00
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 217 ms / 4,000 ms
コード長 7,140 bytes
コンパイル時間 3,684 ms
コンパイル使用メモリ 183,248 KB
実行使用メモリ 14,772 KB
最終ジャッジ日時 2023-10-13 19:49:37
合計ジャッジ時間 10,657 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 2 ms
4,352 KB
testcase_03 AC 2 ms
4,352 KB
testcase_04 AC 2 ms
4,352 KB
testcase_05 AC 2 ms
4,352 KB
testcase_06 AC 1 ms
4,348 KB
testcase_07 AC 2 ms
4,348 KB
testcase_08 AC 1 ms
4,348 KB
testcase_09 AC 2 ms
4,352 KB
testcase_10 AC 2 ms
4,348 KB
testcase_11 AC 9 ms
12,288 KB
testcase_12 AC 66 ms
12,332 KB
testcase_13 AC 86 ms
12,280 KB
testcase_14 AC 125 ms
12,380 KB
testcase_15 AC 150 ms
12,524 KB
testcase_16 AC 155 ms
12,748 KB
testcase_17 AC 133 ms
14,552 KB
testcase_18 AC 161 ms
13,568 KB
testcase_19 AC 84 ms
13,300 KB
testcase_20 AC 15 ms
12,984 KB
testcase_21 AC 156 ms
13,136 KB
testcase_22 AC 180 ms
14,348 KB
testcase_23 AC 117 ms
14,632 KB
testcase_24 AC 146 ms
14,544 KB
testcase_25 AC 211 ms
14,560 KB
testcase_26 AC 217 ms
14,544 KB
testcase_27 AC 19 ms
14,560 KB
testcase_28 AC 207 ms
14,772 KB
testcase_29 AC 212 ms
14,544 KB
testcase_30 AC 18 ms
14,560 KB
testcase_31 AC 212 ms
14,536 KB
testcase_32 AC 187 ms
14,544 KB
testcase_33 AC 185 ms
14,764 KB
testcase_34 AC 192 ms
14,584 KB
testcase_35 AC 186 ms
14,564 KB
testcase_36 AC 180 ms
14,568 KB
testcase_37 AC 177 ms
14,568 KB
testcase_38 AC 171 ms
14,556 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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);
// }
0