#699215 (C++17) No.1698 Face to Face

提出ソース
結果

問題	No.1698 Face to Face
ユーザー	LayCurse
提出日時	2021-09-12 20:00:29
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	3,493 ms / 5,000 ms
コード長	29,512 bytes
コンパイル時間	4,226 ms
コンパイル使用メモリ	253,352 KB
実行使用メモリ	24,704 KB
最終ジャッジ日時	2024-07-19 09:54:40
合計ジャッジ時間	41,783 ms
ジャッジサーバーID （参考情報）	judge5 / judge4
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	76 ms 24,576 KB
testcase_04	AC	262 ms 24,448 KB
testcase_05	AC	847 ms 24,192 KB
testcase_06	AC	743 ms 24,320 KB
testcase_07	AC	295 ms 24,192 KB
testcase_08	AC	315 ms 24,192 KB
testcase_09	AC	316 ms 24,192 KB
testcase_10	AC	226 ms 24,192 KB
testcase_11	AC	1,155 ms 24,192 KB
testcase_12	AC	771 ms 24,244 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
testcase_15	AC	3,457 ms 24,704 KB
testcase_16	AC	3,443 ms 24,704 KB
testcase_17	AC	3,493 ms 24,616 KB
testcase_18	AC	2,445 ms 22,272 KB
testcase_19	AC	1,861 ms 21,984 KB
testcase_20	AC	748 ms 21,248 KB
testcase_21	AC	1,106 ms 13,312 KB
testcase_22	AC	482 ms 11,136 KB
testcase_23	AC	28 ms 5,504 KB
testcase_24	AC	795 ms 14,844 KB
testcase_25	AC	1,371 ms 23,296 KB
testcase_26	AC	58 ms 5,376 KB
testcase_27	AC	216 ms 8,832 KB
testcase_28	AC	353 ms 9,472 KB
testcase_29	AC	89 ms 7,680 KB
testcase_30	AC	1,285 ms 16,500 KB
testcase_31	AC	727 ms 13,568 KB
testcase_32	AC	1,926 ms 18,944 KB
testcase_33	AC	1,922 ms 19,128 KB
testcase_34	AC	2,729 ms 23,680 KB
testcase_35	AC	2 ms 5,376 KB
testcase_36	AC	2 ms 5,376 KB
testcase_37	AC	2 ms 5,376 KB
testcase_38	AC	2 ms 5,376 KB
testcase_39	AC	2 ms 5,376 KB
testcase_40	AC	2 ms 5,376 KB
testcase_41	AC	2 ms 5,376 KB
testcase_42	AC	2 ms 5,376 KB
testcase_43	AC	3 ms 5,376 KB
testcase_44	AC	2 ms 5,376 KB
testcase_45	AC	878 ms 24,448 KB
testcase_46	AC	681 ms 24,448 KB
testcase_47	AC	327 ms 24,192 KB
権限があれば一括ダウンロードができます
ソースコード

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> void sortA_L(int N, T1 a[], T2 b[], void *mem = wmem){
  int i;
  pair<T1, T2>*arr;
  walloc1d(&arr, N, &mem);
  for(i=(0);i<(N);i++){
    arr[i].first = a[i];
    arr[i].second = b[i];
  }
  sort(arr, arr+N);
  for(i=(0);i<(N);i++){
    a[i] = arr[i].first;
    b[i] = arr[i].second;
  }
}
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;
  }
}
struct Rand{
  unsigned x;
  unsigned y;
  unsigned z;
  unsigned w;
  Rand(void){
    x=123456789;
    y=362436069;
    z=521288629;
    w=(unsigned)time(NULL);
  }
  Rand(unsigned seed){
    x=123456789;
    y=362436069;
    z=521288629;
    w=seed;
  }
  inline unsigned get(void){
    unsigned t;
    t = (x^(x<<11));
    x=y;
    y=z;
    z=w;
    w = (w^(w>>19))^(t^(t>>8));
    return w;
  }
  inline double getUni(void){
    return get()/4294967296.0;
  }
  inline int get(int a){
    return (int)(a*getUni());
  }
  inline int get(int a, int b){
    return a+(int)((b-a+1)*getUni());
  }
  inline long long get(long long a){
    return(long long)(a*getUni());
  }
  inline long long get(long long a, long long b){
    return a+(long long)((b-a+1)*getUni());
  }
  inline double get(double a, double b){
    return a+(b-a)*getUni();
  }
  inline int getExp(int a){
    return(int)(exp(getUni()*log(a+1.0))-1.0);
  }
  inline int getExp(int a, int b){
    return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  }
}
;
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 my_putchar_unlocked(const int k){
  putchar_unlocked(k);
}
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(const char c[]){
  int i=0;
  for(i=0;c[i]!='\0';i++){
    my_putchar_unlocked(c[i]);
  }
}
template<class S, class T> inline S chmax(S &a, T b){
  if(a<b){
    a=b;
  }
  return a;
}
struct unionFind{
  int*d;
  int N;
  int M;
  inline void malloc(const int n){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
  }
  inline void malloc(const int n, const int fg){
    d = (int*)std::malloc(n*sizeof(int));
    M = n;
    if(fg){
      init(n);
    }
  }
  inline void free(void){
    std::free(d);
  }
  inline void walloc(const int n, void **mem=&wmem){
    walloc1d(&d, n, mem);
    M = n;
  }
  inline void walloc(const int n, const int fg, void **mem=&wmem){
    walloc1d(&d, n, mem);
    M = n;
    if(fg){
      init(n);
    }
  }
  inline void init(const int n){
    int i;
    N = n;
    for(i=(0);i<(n);i++){
      d[i] = -1;
    }
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    int t = a;
    int k;
    while(d[t]>=0){
      t=d[t];
    }
    while(d[a]>=0){
      k=d[a];
      d[a]=t;
      a=k;
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
    }
    else{
      d[b] += d[a];
      d[a] = b;
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](const int a){
    return d[a];
  }
  inline int size(int a){
    a = get(a);
    return -d[a];
  }
  inline int sizeList(int res[]){
    int i;
    int sz=0;
    for(i=(0);i<(N);i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
  inline int comp(int res[], void *mem = wmem){
    int i;
    int sz=0;
    int*cnt;
    walloc1d(&cnt, N, &mem);
    for(i=(0);i<(N);i++){
      cnt[i] = 0;
    }
    for(i=(0);i<(N);i++){
      cnt[get(i)] = 1;
    }
    for(i=(0);i<(N);i++){
      if(cnt[i]){
        cnt[i] = sz++;
      }
    }
    for(i=(0);i<(N);i++){
      res[i] = cnt[get(i)];
    }
    return sz;
  }
}
;
long long cReader_ll(long long mn, long long mx, char nx){
  int i;
  int fg = 0;
  int m = 1;
  int f = -1;
  long long res = 0;
  double tmp = 0;
  for(;;){
    i = my_getchar_unlocked();
    if(fg==0 && i=='-'){
      fg++;
      m = -1;
    }
    else if('0' <= i  &&  i <= '9'){
      fg++;
      if(f == -1){
        f = i - '0';
      }
      res = 10 * res + i - '0';
      tmp = 10 * tmp + i - '0';
      assert(tmp < 1e20);
    }
    else{
      break;
    }
  }
  assert(tmp / 2 <= res);
  assert((m==1 && fg >= 1) || (m==-1 && fg >= 2));
  assert(mn <= m * res  &&  m * res <= mx);
  assert(!(res == 0 && m == -1));
  assert(!(res != 0 && f == 0));
  assert(!(res == 0 && fg >= 2));
  assert(i == nx);
  return m * res;
}
void cReader_eof(){
  int i;
  i = my_getchar_unlocked();
  assert(i == EOF);
}
int N;
int A[100000];
int B[100000];
int Z[100000];
unionFind uf;
unionFind uf1;
unionFind uf2;
vector<int> oobaka(){
  int i;
  int j;
  int k;
  set<vector<int>> a;
  set<vector<int>> b;
  vector<int> res;
  int mx;
  int tmp;
  for(k=(0);k<(N);k++){
    vector<int> v;
    queue<vector<int>> q;
    a.clear();
    b.clear();
    mx = 0;
    v.clear();
    for(i=(0);i<(N);i++){
      v.push_back(A[i]);
    }
    while(q.size()){
      q.pop();
    }
    q.push(v);
    a.insert(v);
    while(q.size()){
      v = q.front();
      q.pop();
      for(i=(1);i<(N);i++){
        if(v[i-1] <= k && v[i] <= k){
          swap(v[i-1], v[i]);
          if(a.count(v)==0){
            q.push(v);
            a.insert(v);
          }
          swap(v[i-1], v[i]);
        }
      }
    }
    v.clear();
    for(i=(0);i<(N);i++){
      v.push_back(B[i]);
    }
    while(q.size()){
      q.pop();
    }
    q.push(v);
    b.insert(v);
    while(q.size()){
      v = q.front();
      q.pop();
      for(i=(1);i<(N);i++){
        if(v[i-1] <= k && v[i] <= k){
          swap(v[i-1], v[i]);
          if(b.count(v)==0){
            q.push(v);
            b.insert(v);
          }
          swap(v[i-1], v[i]);
        }
      }
    }
    for(auto aa : a){
      for(auto bb : b){
        int x;
        int tmp = 0;
        for(x=(0);x<(N);x++){
          for(i=(0);i<(N);i++){
            if(aa[i]==x){
              break;
            }
          }
          for(j=(0);j<(N);j++){
            if(bb[j]==Z[x]){
              break;
            }
          }
          if(i==j){
            tmp++;
          }
        }
        chmax(mx, tmp);
      }
    }
    res.push_back(mx);
  }
  return res;
}
vector<int> baka(){
  int i;
  int j;
  int k;
  vector<int> res;
  for(k=(0);k<(N);k++){
    int m;
    uf1.init(N);
    uf2.init(N);
    int use[N] = {};
    int tmp = 0;
    for(i=(1);i<(N);i++){
      if(A[i-1] <= k && A[i] <= k){
        uf1(i-1, i);
      }
    }
    for(i=(1);i<(N);i++){
      if(B[i-1] <= k && B[i] <= k){
        uf2(i-1, i);
      }
    }
    for(m=(0);m<(N);m++){
      int x;
      for(i=(0);i<(N);i++){
        if(A[i] == m){
          break;
        }
      }
      for(j=(0);j<(N);j++){
        if(B[j] == Z[m]){
          break;
        }
      }
      for(x=(0);x<(N);x++){
        if(!use[x] && uf1(i) == uf1(x) && uf2(j) == uf2(x)){
          tmp++;
          use[x] = 1;
          break;
        }
      }
    }
    res.push_back(tmp);
  }
  return res;
}
struct RBMM{
  int mn;
  int mx;
}
;
struct RBV{
  int mn;
  int mx;
  int v;
}
;
RBMM rollbackUnionFind_md_func(RBMM a, RBMM b){
  return {min_L(a.mn, b.mn),max_L(a.mx, b.mx)};
}
RBV rollbackUnionFind_md_func(RBV a, RBV b){
  return {min_L(a.mn, b.mn),max_L(a.mx, b.mx), a.v + b.v};
}
template<class T> struct rollbackUnionFind_md{
  int*d;
  int N;
  int M;
  int*h1;
  int*h2;
  int sz;
  int snapsz;
  T*v;
  T*h3;
  inline void malloc(const int n){
    d = (int*)std::malloc(n*sizeof(int));
    h1 = (int*)std::malloc(2*n*sizeof(int));
    h2 = (int*)std::malloc(2*n*sizeof(int));
    v = (T*)std::malloc(n*sizeof(T));
    h3 = (T*)std::malloc(2*n*sizeof(T));
    M = n;
  }
  inline void malloc(const int n, const int fg){
    d = (int*)std::malloc(n*sizeof(int));
    h1 = (int*)std::malloc(2*n*sizeof(int));
    h2 = (int*)std::malloc(2*n*sizeof(int));
    v = (T*)std::malloc(n*sizeof(T));
    h3 = (T*)std::malloc(2*n*sizeof(T));
    M = n;
    if(fg){
      init(n);
    }
  }
  inline void free(void){
    std::free(d);
    std::free(h1);
    std::free(h2);
    std::free(v);
    std::free(h3);
  }
  inline void walloc(const int n, void **mem=&wmem){
    walloc1d(&d, n, mem);
    walloc1d(&h1, 2*n, mem);
    walloc1d(&h2, 2*n, mem);
    walloc1d(&v, n, mem);
    walloc1d(&h3, 2*n, mem);
    M = n;
  }
  inline void walloc(const int n, const int fg, void **mem=&wmem){
    walloc1d(&d, n, mem);
    walloc1d(&h1, 2*n, mem);
    walloc1d(&h2, 2*n, mem);
    walloc1d(&v, n, mem);
    walloc1d(&h3, 2*n, mem);
    M = n;
    if(fg){
      init(n);
    }
  }
  inline void init(const int n){
    int i;
    N = n;
    for(i=(0);i<(n);i++){
      d[i] = -1;
    }
    sz = 0;
    snapsz = 0;
  }
  inline void init(void){
    init(M);
  }
  inline int get(int a){
    while(d[a]>=0){
      a=d[a];
    }
    return a;
  }
  inline int connect(int a, int b){
    if(d[a]>=0){
      a=get(a);
    }
    if(d[b]>=0){
      b=get(b);
    }
    if(a==b){
      return 0;
    }
    h1[sz] = a;
    h2[sz] = d[a];
    h3[sz] = v[a];
    sz++;
    h1[sz] = b;
    h2[sz] = d[b];
    h3[sz] = v[b];
    sz++;
    if(d[a] < d[b]){
      d[a] += d[b];
      d[b] = a;
      v[a] = rollbackUnionFind_md_func(v[a], v[b]);
    }
    else{
      d[b] += d[a];
      d[a] = b;
      v[b] = rollbackUnionFind_md_func(v[a], v[b]);
    }
    return 1;
  }
  inline int operator()(int a){
    return get(a);
  }
  inline int operator()(int a, int b){
    return connect(a,b);
  }
  inline int& operator[](const int a){
    return d[a];
  }
  inline int size(int a){
    a = get(a);
    return -d[a];
  }
  inline int sizeList(int res[]){
    int i;
    int sz=0;
    for(i=(0);i<(N);i++){
      if(d[i]<0){
        res[sz++] = -d[i];
      }
    }
    return sz;
  }
  inline int undo(void){
    if(sz==0){
      return 0;
    }
    sz--;
    d[h1[sz]] = h2[sz];
    v[h1[sz]] = h3[sz];
    sz--;
    d[h1[sz]] = h2[sz];
    v[h1[sz]] = h3[sz];
    if(snapsz > sz){
      snapsz = sz;
    }
    return 1;
  }
  inline void snapshot(void){
    snapsz = sz;
  }
  inline void rollback(void){
    while(snapsz < sz){
      sz--;
      d[h1[sz]] = h2[sz];
      v[h1[sz]] = h3[sz];
      sz--;
      d[h1[sz]] = h2[sz];
      v[h1[sz]] = h3[sz];
    }
  }
  inline T getVal(int a){
    a = get(a);
    return v[a];
  }
  inline void setVal(int a, T val){
    a = get(a);
    v[a] = val;
  }
}
;
rollbackUnionFind_md<RBMM> ruf1;
rollbackUnionFind_md<RBMM> ruf2;
rollbackUnionFind_md<RBV> ruf;
int invA[100000];
int invB[100000];
int ftm[100000];
int plc[100000];
int ind[100000];
int liss[20][100000];
int ok[100000];
int solve_uf_doit_sub(int i, int j){
  int res = 0;
  RBV v;
  if(ruf(i) != ruf(j)){
    v = ruf.getVal(i);
    res -=min_L(v.v, v.mx - v.mn + 1);
    v = ruf.getVal(j);
    res -=min_L(v.v, v.mx - v.mn + 1);
    ruf(i,j);
    v = ruf.getVal(i);
    res +=min_L(v.v, v.mx - v.mn + 1);
  }
  return res;
}
int solve_uf_doit(int i){
  int x;
  int res = 0;
  RBV v;
  x = invA[i];
  if(x-1 >= 0 && A[x-1] <= i){
    ruf1(x-1,x);
    if(ruf2(x-1) == ruf2(x)){
      res += solve_uf_doit_sub(x-1, x);
    }
  }
  if(x+1 < N && A[x+1] <= i){
    ruf1(x,x+1);
    if(ruf2(x) == ruf2(x+1)){
      res += solve_uf_doit_sub(x, x+1);
    }
  }
  x = invB[i];
  if(x-1 >= 0 && B[x-1] <= i){
    ruf2(x-1,x);
    if(ruf1(x-1) == ruf1(x)){
      res += solve_uf_doit_sub(x-1, x);
    }
  }
  if(x+1 < N && B[x+1] <= i){
    ruf2(x,x+1);
    if(ruf1(x) == ruf1(x+1)){
      res += solve_uf_doit_sub(x, x+1);
    }
  }
  return res;
}
void solve_uf_doit2(int i){
  int x;
  x = invA[i];
  if(x-1 >= 0 && A[x-1] <= i){
    ruf1(x-1,x);
  }
  if(x+1 < N && A[x+1] <= i){
    ruf1(x,x+1);
  }
  x = invB[i];
  if(x-1 >= 0 && B[x-1] <= i){
    ruf2(x-1,x);
  }
  if(x+1 < N && B[x+1] <= i){
    ruf2(x,x+1);
  }
}
void solve_sub(int s, int e, int sz, int *lis, int dep){
  int i;
  int j;
  int k;
  int ss;
  int m;
  int sz1;
  int sz2;
  int x;
  int y;
  int b = 500;
  int*chk = liss[10];
  for(ss=(0);ss<(N);ss+=(b)){
    s = ss;
    e =min_L(ss + b, N);
    for(i=(s);i<(e);i++){
      solve_uf_doit2(i);
    }
    sz1 = sz2 = 0;
    for(i=(0);i<(sz);i++){
      x =max_L(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
      y =min_L(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
      if(x <= y){
        chk[sz1++]= lis[i];
      }
      else{
        lis[sz2++]= lis[i];
      }
    }
    if(sz1){
      ruf1.rollback();
      ruf2.rollback();
      for(k=(s);k<(e);k++){
        solve_uf_doit2(k);
        for(i=(0);i<(sz1);i++){
          if(!ok[chk[i]]){
            x =max_L(ruf1.getVal(invA[chk[i]]).mn, ruf2.getVal(invB[Z[chk[i]]]).mn);
            y =min_L(ruf1.getVal(invA[chk[i]]).mx, ruf2.getVal(invB[Z[chk[i]]]).mx);
            if(x <= y){
              ftm[chk[i]] = k;
              plc[chk[i]] = x;
              ok[chk[i]] = 1;
            }
          }
        }
      }
    }
    sz = sz2;
    ruf1.snapshot();
    ruf2.snapshot();
  }
}
vector<int> solve(){
  int i;
  int j;
  int k;
  vector<int> res(N);
  RBV v;
  int resval;
  ruf1.init(N);
  ruf2.init(N);
  ruf.init(N);
  for(i=(0);i<(N);i++){
    ruf1.setVal(i, {i,i});
  }
  for(i=(0);i<(N);i++){
    ruf2.setVal(i, {i,i});
  }
  for(i=(0);i<(N);i++){
    ruf.setVal(i, {i,i,0});
  }
  for(i=(0);i<(N);i++){
    invA[A[i]] = i;
  }
  for(i=(0);i<(N);i++){
    invB[B[i]] = i;
  }
  for(i=(0);i<(N);i++){
    liss[0][i] = i;
  }
  solve_sub(0, N, N, liss[0], 0);
  ruf1.init(N);
  ruf2.init(N);
  ruf.init(N);
  for(i=(0);i<(N);i++){
    ruf1.setVal(i, {i,i});
  }
  for(i=(0);i<(N);i++){
    ruf2.setVal(i, {i,i});
  }
  for(i=(0);i<(N);i++){
    ruf.setVal(i, {i,i,0});
  }
  for(i=(0);i<(N);i++){
    ind[i] = i;
  }
  sortA_L(N,ftm,plc,ind);
  k = 0;
  resval = 0;
  for(i=(0);i<(N);i++){
    resval += solve_uf_doit(i);
    while(k < N && ftm[k] == i){
      v = ruf.getVal(plc[k]);
      resval -=min_L(v.v, v.mx - v.mn + 1);
      v.v++;
      resval +=min_L(v.v, v.mx - v.mn + 1);
      ruf.setVal(plc[k], v);
      k++;
    }
    res[i] = resval;
  }
  return res;
}
int cnt[100000];
int main(){
  int i;
  wmem = memarr;
  Rand rnd;
  uf.walloc(100000);
  uf1.walloc(100000);
  uf2.walloc(100000);
  ruf1.walloc(100000);
  ruf2.walloc(100000);
  ruf.walloc(100000);
  N = cReader_ll(2, 100000, '\n');
  for(i=(0);i<(N);i++){
    A[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
  }
  for(i=(0);i<(N);i++){
    B[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
  }
  for(i=(0);i<(N);i++){
    Z[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
  }
  for(i=(0);i<(N);i++){
    cnt[i] = 0;
  }
  for(i=(0);i<(N);i++){
    cnt[A[i]]++;
  }
  for(i=(0);i<(N);i++){
    assert(cnt[i]==1);
  }
  for(i=(0);i<(N);i++){
    cnt[i] = 0;
  }
  for(i=(0);i<(N);i++){
    cnt[B[i]]++;
  }
  for(i=(0);i<(N);i++){
    assert(cnt[i]==1);
  }
  for(i=(0);i<(N);i++){
    cnt[i] = 0;
  }
  for(i=(0);i<(N);i++){
    cnt[Z[i]]++;
  }
  for(i=(0);i<(N);i++){
    assert(cnt[i]==1);
  }
  cReader_eof();
  vector<int> res;
  res = solve();
  {
    int dDIyew82;
    for(dDIyew82=(0);dDIyew82<(N);dDIyew82++){
      wt_L(res[dDIyew82]);
      wt_L('\n');
    }
  }
  return 0;
  puts("");
  for(;;){
    vector<int> r1;
    vector<int> r2;
    vector<int> r3;
    N = rnd.get(2,6);
    for(i=(0);i<(N);i++){
      A[i] = B[i] = Z[i] = i;
    }
    random_shuffle(A,A+N);
    random_shuffle(B,B+N);
    random_shuffle(Z,Z+N);
    wt_L(N);
    wt_L(' ');
    wt_L(":");
    wt_L(' ');
    {
      int dd01qmIa;
      for(dd01qmIa=(0);dd01qmIa<(N);dd01qmIa++){
        wt_L(A[dd01qmIa]);
        wt_L(' ');
      }
    }
    wt_L(":");
    wt_L(' ');
    {
      int Zs_a1Ftk;
      for(Zs_a1Ftk=(0);Zs_a1Ftk<(N);Zs_a1Ftk++){
        wt_L(B[Zs_a1Ftk]);
        wt_L(' ');
      }
    }
    wt_L(":");
    wt_L(' ');
    {
      int B8qxtQZy;
      if(N==0){
        wt_L('\n');
      }
      else{
        for(B8qxtQZy=(0);B8qxtQZy<(N-1);B8qxtQZy++){
          wt_L(Z[B8qxtQZy]);
          wt_L(' ');
        }
        wt_L(Z[B8qxtQZy]);
        wt_L('\n');
      }
    }
    r1 = oobaka();
    r2 = baka();
    r3 = solve();
    {
      int pRrsnthG;
      if(N==0){
        wt_L('\n');
      }
      else{
        for(pRrsnthG=(0);pRrsnthG<(N-1);pRrsnthG++){
          wt_L(r1[pRrsnthG]);
          wt_L(' ');
        }
        wt_L(r1[pRrsnthG]);
        wt_L('\n');
      }
    }
    {
      int Vdr_4aft;
      if(N==0){
        wt_L('\n');
      }
      else{
        for(Vdr_4aft=(0);Vdr_4aft<(N-1);Vdr_4aft++){
          wt_L(r2[Vdr_4aft]);
          wt_L(' ');
        }
        wt_L(r2[Vdr_4aft]);
        wt_L('\n');
      }
    }
    {
      int Ly6DsuN0;
      if(N==0){
        wt_L('\n');
      }
      else{
        for(Ly6DsuN0=(0);Ly6DsuN0<(N-1);Ly6DsuN0++){
          wt_L(r3[Ly6DsuN0]);
          wt_L(' ');
        }
        wt_L(r3[Ly6DsuN0]);
        wt_L('\n');
      }
    }
    assert(r1==r2);
    assert(r2==r3);
  }
  return 0;
}
// cLay version 20210904-1

// --- original code ---
// int N, A[1d5], B[], Z[];
// unionFind uf, uf1, uf2;
// 
// VI oobaka(){
//   int i, j, k;
//   set<VI> a, b;
//   VI res;
//   int mx, tmp;
//   rep(k,N){
//     VI v;
//     queue<VI> q;
//     a.clear();
//     b.clear();
// 
//     mx = 0;
// 
//     v.clear();
//     rep(i,N) v.push_back(A[i]);
//     while(q.size()) q.pop();
//     q.push(v);
//     a.insert(v);
//     while(q.size()){
//       v = q.front();
//       q.pop();
//       rep(i,1,N) if(v[i-1] <= k && v[i] <= k){
//         swap(v[i-1], v[i]);
//         if(a.count(v)==0) q.push(v), a.insert(v);
//         swap(v[i-1], v[i]);
//       }
//     }
// 
//     v.clear();
//     rep(i,N) v.push_back(B[i]);
//     while(q.size()) q.pop();
//     q.push(v);
//     b.insert(v);
//     while(q.size()){
//       v = q.front();
//       q.pop();
//       rep(i,1,N) if(v[i-1] <= k && v[i] <= k){
//         swap(v[i-1], v[i]);
//         if(b.count(v)==0) q.push(v), b.insert(v);
//         swap(v[i-1], v[i]);
//       }
//     }
// 
//     for(auto aa : a) for(auto bb : b){
//       int tmp = 0;
//       rep(x,N){
//         rep(i,N) if(aa[i]==x) break;
//         rep(j,N) if(bb[j]==Z[x]) break;
//         if(i==j) tmp++;
//       }
//       mx >?= tmp;
//     }
// 
//     res.push_back(mx);
//   }
//   return res;
// }
// 
// VI baka(){
//   int i, j, k;
//   VI res;
//   rep(k,N){
//     uf1.init(N);
//     uf2.init(N);
//     int use[N] = {}, tmp = 0;
// 
//     rep(i,1,N) if(A[i-1] <= k && A[i] <= k) uf1(i-1, i);
//     rep(i,1,N) if(B[i-1] <= k && B[i] <= k) uf2(i-1, i);
// 
//     rep(m,N){
//       rep(i,N) if(A[i] == m) break;
//       rep(j,N) if(B[j] == Z[m]) break;
//       rep(x,N) if(!use[x] && uf1(i) == uf1(x) && uf2(j) == uf2(x)){
//         tmp++;
//         use[x] = 1;
//         break;
//       }
//     }
// 
//     res.push_back(tmp);
//   }
//   return res;
// }
// 
// 
// 
// 
// struct RBMM {int mn, mx;};
// struct RBV {int mn, mx, v;};
// 
// RBMM rollbackUnionFind_md_func(RBMM a, RBMM b){
//   return {min(a.mn, b.mn), max(a.mx, b.mx)};
// }
// 
// RBV rollbackUnionFind_md_func(RBV a, RBV b){
//   return {min(a.mn, b.mn), max(a.mx, b.mx), a.v + b.v};
// }
// 
// template<class T>
// struct rollbackUnionFind_md{
//   int *d, N, M;
//   int *h1, *h2, sz, snapsz;
//   T *v, *h3;
//   inline void malloc(const int n){
//     d = (int*)std::malloc(n*sizeof(int));
//     h1 = (int*)std::malloc(2*n*sizeof(int));
//     h2 = (int*)std::malloc(2*n*sizeof(int));
//     v = (T*)std::malloc(n*sizeof(T));
//     h3 = (T*)std::malloc(2*n*sizeof(T));
//     M = n;
//   }
//   inline void malloc(const int n, const int fg){
//     d = (int*)std::malloc(n*sizeof(int));
//     h1 = (int*)std::malloc(2*n*sizeof(int));
//     h2 = (int*)std::malloc(2*n*sizeof(int));
//     v = (T*)std::malloc(n*sizeof(T));
//     h3 = (T*)std::malloc(2*n*sizeof(T));
//     M = n;
//     if(fg) init(n);
//   }
//   inline void free(void){
//     std::free(d);
//     std::free(h1);
//     std::free(h2);
//     std::free(v);
//     std::free(h3);
//   }
//   inline void walloc(const int n, void **mem=&wmem){
//     walloc1d(&d, n, mem);
//     walloc1d(&h1, 2*n, mem);
//     walloc1d(&h2, 2*n, mem);
//     walloc1d(&v, n, mem);
//     walloc1d(&h3, 2*n, mem);
//     M = n;
//   }
//   inline void walloc(const int n, const int fg, void **mem=&wmem){
//     walloc1d(&d, n, mem);
//     walloc1d(&h1, 2*n, mem);
//     walloc1d(&h2, 2*n, mem);
//     walloc1d(&v, n, mem);
//     walloc1d(&h3, 2*n, mem);
//     M = n;
//     if(fg) init(n);
//   }
//   inline void init(const int n){
//     int i;
//     N = n;
//     rep(i,n) d[i] = -1;
//     sz = 0;
//     snapsz = 0;
//   }
//   inline void init(void){
//     init(M);
//   }
//   inline int get(int a){
//     while(d[a]>=0) a=d[a];
//     return a;
//   }
//   inline int connect(int a, int b){
//     if(d[a]>=0) a=get(a);
//     if(d[b]>=0) b=get(b);
//     if(a==b) return 0;
//     h1[sz] = a; h2[sz] = d[a]; h3[sz] = v[a]; sz++;
//     h1[sz] = b; h2[sz] = d[b]; h3[sz] = v[b]; sz++;
//     if(d[a] < d[b]) d[a] += d[b], d[b] = a, v[a] = rollbackUnionFind_md_func(v[a], v[b]);
//     else            d[b] += d[a], d[a] = b, v[b] = rollbackUnionFind_md_func(v[a], v[b]);
//     return 1;
//   }
//   inline int operator()(int a){
//     return get(a);
//   }
//   inline int operator()(int a, int b){
//     return connect(a,b);
//   }
//   inline int& operator[](const int a){
//     return d[a];
//   }
//   inline int size(int a){
//     a = get(a);
//     return -d[a];
//   }
//   inline int sizeList(int res[]){
//     int i, sz=0;
//     rep(i,N) if(d[i]<0) res[sz++] = -d[i];
//     return sz;
//   }
//   inline int undo(void){
//     if(sz==0) return 0;
//     sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
//     sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
//     if(snapsz > sz) snapsz = sz;
//     return 1;
//   }
//   inline void snapshot(void){
//     snapsz = sz;
//   }
//   inline void rollback(void){
//     while(snapsz < sz){
//       sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
//       sz--; d[h1[sz]] = h2[sz]; v[h1[sz]] = h3[sz];
//     }
//   }
//   inline T getVal(int a){
//     a = get(a);
//     return v[a];
//   }
//   inline void setVal(int a, T val){
//     a = get(a);
//     v[a] = val;
//   }
// };
// 
// 
// rollbackUnionFind_md<RBMM> ruf1, ruf2;
// rollbackUnionFind_md<RBV> ruf;
// 
// int invA[1d5], invB[1d5];
// int ftm[1d5], plc[1d5], ind[1d5];
// int liss[20][1d5], ok[1d5];
// 
// int solve_uf_doit_sub(int i, int j){
//   int res = 0;
//   RBV v;
//   if(ruf(i) != ruf(j)){
//     v = ruf.getVal(i);
//     res -= min(v.v, v.mx - v.mn + 1);
//     v = ruf.getVal(j);
//     res -= min(v.v, v.mx - v.mn + 1);
//     ruf(i,j);
//     v = ruf.getVal(i);
//     res += min(v.v, v.mx - v.mn + 1);
//   }
//   return res;
// }
// 
// int solve_uf_doit(int i){
//   int x, res = 0;
//   RBV v;
//   x = invA[i];
//   if(x-1 >= 0 && A[x-1] <= i){
//     ruf1(x-1,x);
//     if(ruf2(x-1) == ruf2(x)) res += solve_uf_doit_sub(x-1, x);
//   }
//   if(x+1 < N && A[x+1] <= i){
//     ruf1(x,x+1);
//     if(ruf2(x) == ruf2(x+1)) res += solve_uf_doit_sub(x, x+1);
//   }
//   x = invB[i];
//   if(x-1 >= 0 && B[x-1] <= i){
//     ruf2(x-1,x);
//     if(ruf1(x-1) == ruf1(x)) res += solve_uf_doit_sub(x-1, x);
//   }
//   if(x+1 < N && B[x+1] <= i){
//     ruf2(x,x+1);
//     if(ruf1(x) == ruf1(x+1)) res += solve_uf_doit_sub(x, x+1);
//   }
//   return res;
// }
// 
// void solve_uf_doit2(int i){
//   int x;
//   x = invA[i];
//   if(x-1 >= 0 && A[x-1] <= i){
//     ruf1(x-1,x);
//   }
//   if(x+1 < N && A[x+1] <= i){
//     ruf1(x,x+1);
//   }
//   x = invB[i];
//   if(x-1 >= 0 && B[x-1] <= i){
//     ruf2(x-1,x);
//   }
//   if(x+1 < N && B[x+1] <= i){
//     ruf2(x,x+1);
//   }
// }
// 
// void solve_sub(int s, int e, int sz, int *lis, int dep){
//   int i, j, k, ss, m, sz1, sz2, x, y, b = 500;
//   int *chk = liss[10];
// 
//   rep(ss,0,N,b){
//     s = ss;
//     e = min(ss + b, N);
// 
//     rep(i,s,e) solve_uf_doit2(i);
// 
//     sz1 = sz2 = 0;
//     rep(i,sz){
//       x = max(ruf1.getVal(invA[lis[i]]).mn, ruf2.getVal(invB[Z[lis[i]]]).mn);
//       y = min(ruf1.getVal(invA[lis[i]]).mx, ruf2.getVal(invB[Z[lis[i]]]).mx);
//       if[x <= y, chk[sz1++], lis[sz2++]] = lis[i];
//     }
// 
//     if(sz1){
//       ruf1.rollback();
//       ruf2.rollback();
//       rep(k,s,e){
//         solve_uf_doit2(k);
//         rep(i,sz1) if(!ok[chk[i]]){
//           x = max(ruf1.getVal(invA[chk[i]]).mn, ruf2.getVal(invB[Z[chk[i]]]).mn);
//           y = min(ruf1.getVal(invA[chk[i]]).mx, ruf2.getVal(invB[Z[chk[i]]]).mx);
//           if(x <= y){
//             ftm[chk[i]] = k;
//             plc[chk[i]] = x;
//             ok[chk[i]] = 1;
//           }
//         }
//       }
//     }
// 
//     sz = sz2;
//     ruf1.snapshot();
//     ruf2.snapshot();
//   }
// }
// 
// VI solve(){
//   int i, j, k;
//   VI res(N);
//   RBV v;
//   int resval;
// 
//   ruf1.init(N);
//   ruf2.init(N);
//   ruf.init(N);
//   rep(i,N) ruf1.setVal(i, {i,i});
//   rep(i,N) ruf2.setVal(i, {i,i});
//   rep(i,N) ruf.setVal(i, {i,i,0});
// 
//   rep(i,N) invA[A[i]] = i;
//   rep(i,N) invB[B[i]] = i;
// 
//   rep(i,N) liss[0][i] = i;
//   solve_sub(0, N, N, liss[0], 0);
// 
//   ruf1.init(N);
//   ruf2.init(N);
//   ruf.init(N);
//   rep(i,N) ruf1.setVal(i, {i,i});
//   rep(i,N) ruf2.setVal(i, {i,i});
//   rep(i,N) ruf.setVal(i, {i,i,0});
// 
//   rep(i,N) ind[i] = i;
//   sortA(N,ftm,plc,ind);
// 
//   // rep(i,N) wt(ind[i],ftm[i],plc[i]);
// 
//   k = 0;
//   resval = 0;
//   rep(i,N){
//     resval += solve_uf_doit(i);
//     while(k < N && ftm[k] == i){
//       v = ruf.getVal(plc[k]);
//       // wt(i,":",ind[k],":",v.mn,v.mx,v.v);
//       resval -= min(v.v, v.mx - v.mn + 1);
//       v.v++;
//       resval += min(v.v, v.mx - v.mn + 1);
//       ruf.setVal(plc[k], v);
//       k++;
//     }
//     res[i] = resval;
//   }
// 
//   return res;
// }
// 
// 
// int cnt[1d5];
// {
//   Rand rnd;
//   uf.walloc(1d5);
//   uf1.walloc(1d5);
//   uf2.walloc(1d5);
// 
//   ruf1.walloc(1d5);
//   ruf2.walloc(1d5);
//   ruf.walloc(1d5);
// 
//   N = cReader_ll(2, 1d5, '\n');
//   rep(i,N) A[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
//   rep(i,N) B[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
//   rep(i,N) Z[i] = cReader_ll(1, N, i==N-1?'\n':' ') - 1;
// 
//   rep(i,N) cnt[i] = 0;
//   rep(i,N) cnt[A[i]]++;
//   rep(i,N) assert(cnt[i]==1);
//   rep(i,N) cnt[i] = 0;
//   rep(i,N) cnt[B[i]]++;
//   rep(i,N) assert(cnt[i]==1);
//   rep(i,N) cnt[i] = 0;
//   rep(i,N) cnt[Z[i]]++;
//   rep(i,N) assert(cnt[i]==1);
// 
//   cReader_eof();
// 
//   VI res;
//   res = solve();
//   wtLn(res(N));
//   return 0;
// 
//   puts("");
//   for(;;){
//     VI r1, r2, r3;
//     N = rnd.get(2,6);
//     rep(i,N) A[i] = B[i] = Z[i] = i;
//     random_shuffle(A,A+N);
//     random_shuffle(B,B+N);
//     random_shuffle(Z,Z+N);
// 
//     wt(N,":",A(N),":",B(N),":",Z(N));
//     r1 = oobaka();
//     r2 = baka();
//     r3 = solve();
//     wt(r1(N));
//     wt(r2(N));
//     wt(r3(N));
//     assert(r1==r2);
//     assert(r2==r3);
//   }
// 
// }
yukicoder

結果

テストケース

ソースコード
