結果

問題 No.1698 Face to Face
ユーザー Xiaohuba
提出日時 2025-05-24 21:55:35
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 431 ms / 5,000 ms
コード長 6,599 bytes
コンパイル時間 2,261 ms
コンパイル使用メモリ 214,512 KB
実行使用メモリ 32,060 KB
最終ジャッジ日時 2025-05-24 21:55:50
合計ジャッジ時間 11,418 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128
// #undef DEBUG

#ifdef DEBUG
#include <moeebius/debug.hpp>
#else
#define debug(...) (void(0))
#define Debug(...) (void(0))
#endif

#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif

#if !defined(_WIN32) && !defined(__CYGWIN__) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define ssz(x) (signed((x).size()))
#define beg2ed(x) (x).begin(), (x).end()
#define _loop_i_t(j, k) make_signed_t<decltype((j) - (k))>
#define For(i, j, k) for (_loop_i_t(j, k) i = (j); i <= (k); ++i)
#define ForDown(i, j, k) for (_loop_i_t(j, k) i = (j); i >= decltype(i)(k); --i)
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
constexpr il ll qpow(ll x, ull y, ll mod){ ll ans = 1; x %= mod; while (y) { if (y & 1) (ans *= x) %= mod; (x *= x) %= mod; y >>= 1; } return ans; }
template<typename T> constexpr il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> constexpr il void cmax(T & x, const T &y){ x = max(x, y); }
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while (!isdigit(c)) { if (c == '-') f = -1; c = getchar(); } while (isdigit(c)) { x = x * 10 + (c - '0'); c = getchar(); } x *= f; }
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x), read(y...); }
// clang-format on

// File head end

namespace {
constexpr ll MAXN = 1e5 + 5;
int n, a[MAXN], b[MAXN], p[MAXN], q[MAXN], pos1[MAXN], pos2[MAXN], f1[MAXN],
    f2[MAXN];
pii seg1[MAXN], seg2[MAXN];
set<int> S1[MAXN], S2[MAXN];
bool vis[MAXN];
int find1(int x) { return f1[x] == x ? x : f1[x] = find1(f1[x]); }
int find2(int x) {
  // cerr << x << '\n';
  return f2[x] == x ? x : f2[x] = find2(f2[x]);
}
void merge(set<int> &x, set<int> &y) {
  if (ssz(x) < ssz(y))
    x.swap(y);
  x.insert(beg2ed(y)), y.clear();
}
int getL1(int lim) {
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (seg2[find2(mid)].fi >= lim)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return r + 1;
}
int getL2(int lim) {
  int l = 1, r = n;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (seg1[find1(mid)].fi >= lim)
      r = mid - 1;
    else
      l = mid + 1;
  }
  return r + 1;
}
void Main() {
  read(n);
  For(i, 1, n) read(a[i]), pos1[a[i]] = i;
  For(i, 1, n) read(b[i]), pos2[b[i]] = i;
  For(i, 1, n) read(p[i]), q[p[i]] = i;

  iota(f1 + 1, f1 + 1 + n, 1);
  iota(f2 + 1, f2 + 1 + n, 1);
  int ans = 0;
  set<int> U;
  For(i, 1, n) U.emplace(i);
  For(i, 1, n) {
    seg1[i] = seg2[i] = {i, i};
    if (b[i] != p[a[i]])
      S1[i].emplace(pos2[p[a[i]]]), S2[i].emplace(pos1[q[b[i]]]);
    else
      vis[a[i]] = 1, ans++, U.erase(i);
  }
  cout << ans << '\n';
  For(t, 2, n) {
    int x = pos1[t];
    if (x > 1 && a[x - 1] < t) {
      int y = find1(x - 1);
      seg1[x].fi = seg1[y].fi, f1[y] = x;
      merge(S1[x], S1[y]);
    }
    if (x < n && a[x + 1] < t) {
      int y = find1(x + 1);
      seg1[x].se = seg1[y].se, f1[y] = x;
      merge(S1[x], S1[y]);
    }
    int L = getL1(seg1[x].fi);
    set<int>::iterator it;
    while ((it = S1[x].lower_bound(L)) != S1[x].end()) {
      int u = *it;
      if (seg2[find2(u)].fi > seg1[x].se)
        break;
      auto it2 = U.lower_bound(seg2[find2(u)].fi);
      if (it2 == U.end() || *it2 > seg1[x].se)
        break;
      S1[x].erase(it);
      if (*it2 > seg2[find2(u)].se)
        continue;
      // cerr << "A " << t << ' ' << q[b[u]] << ' ' << p[q[b[u]]] << '\n';
      assert(!vis[q[b[u]]]);
      int val = q[b[u]];
      vis[val] = 1, ans++;
      S2[find2(u)].erase(pos1[val]), U.erase(it2);
    }
    while (1) {
      it = S1[x].lower_bound(L);
      if (it == S1[x].begin() || seg2[find2(*prev(it))].se < seg1[x].fi)
        break;
      int u = *--it;
      auto it2 = U.lower_bound(seg1[x].fi);
      if (it2 == U.end() || *it2 > min(seg1[x].se, seg2[find2(u)].se))
        break;
      S1[x].erase(it);
      // cerr << "B " << t << ' ' << q[b[u]] << ' ' << p[q[b[u]]] << '\n';
      assert(!vis[q[b[u]]]);
      int val = q[b[u]];
      vis[val] = 1, ans++;
      S2[find2(u)].erase(pos1[val]), U.erase(it2);
    }

    x = pos2[t];
    if (x > 1 && b[x - 1] < t) {
      int y = find2(x - 1);
      seg2[x].fi = seg2[y].fi, f2[y] = x;
      merge(S2[x], S2[y]);
    }
    if (x < n && b[x + 1] < t) {
      int y = find2(x + 1);
      seg2[x].se = seg2[y].se, f2[y] = x;
      merge(S2[x], S2[y]);
    }
    L = getL2(seg2[x].fi);
    while ((it = S2[x].lower_bound(L)) != S2[x].end()) {
      int u = *it;
      if (seg1[find1(u)].fi > seg2[x].se)
        break;
      auto it2 = U.lower_bound(seg1[find1(u)].fi);
      if (it2 == U.end() || *it2 > seg2[x].se)
        break;
      S2[x].erase(it);
      if (*it2 > seg1[find1(u)].se)
        continue;
      assert(!vis[a[u]]);
      int val = a[u];
      vis[val] = 1, ans++;
      // cerr << "C " << t << ' ' << val << ' ' << p[val] << '\n';
      // assert(S1[find1(u)].count(pos2[p[val]]));
      S1[find1(u)].erase(pos2[p[val]]), U.erase(it2);
    }
    while (1) {
      it = S2[x].lower_bound(L);
      if (it == S2[x].begin() || seg1[find1(*prev(it))].se < seg2[x].fi)
        break;
      int u = *--it;
      auto it2 = U.lower_bound(seg2[x].fi);
      if (it2 == U.end() || *it2 > min(seg2[x].se, seg1[find1(u)].se))
        break;
      S2[x].erase(it);
      assert(!vis[a[u]]);
      int val = a[u];
      vis[val] = 1, ans++;
      // cerr << "D " << t << ' ' << val << ' ' << p[val] << '\n';
      S1[find1(u)].erase(pos2[p[val]]), U.erase(it2);
    }

    printf("%d\n", ans);
  }
}
} // namespace

signed main() { return Main(), 0; }
0