結果

問題 No.1698 Face to Face
コンテスト
ユーザー December456
提出日時 2025-05-27 17:20:12
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 733 ms / 5,000 ms
コード長 3,923 bytes
コンパイル時間 1,012 ms
コンパイル使用メモリ 57,348 KB
実行使用メモリ 36,780 KB
最終ジャッジ日時 2025-05-27 17:20:36
合計ジャッジ時間 17,631 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 45
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:161:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  161 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:164:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  164 |         scanf("%d", &a[i]);
      |         ~~~~~^~~~~~~~~~~~~
main.cpp:169:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  169 |         scanf("%d", &b[i]);
      |         ~~~~~^~~~~~~~~~~~~
main.cpp:174:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
  174 |         scanf("%d", &p[i]);
      |         ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#include <set>
#include <cstdio>

constexpr int MAX_N = 100000 + 2;
constexpr int MAX_LOG_N = 16 + 2;

int n, ans, pA[MAX_N], pB[MAX_N];
int p[MAX_N], a[MAX_N], b[MAX_N];

bool validA[MAX_N], validB[MAX_N];

std::set<std::pair<int, int>> A, B;

struct Node {
    int ls, rs, cnt;
};

class SegmentTree {
  public:
    int nodeId, rt[MAX_N];
    Node t[MAX_N * MAX_LOG_N];

    void insert(int &o1, int o2, int l, int r, int x) {
        t[o1 = ++nodeId] = t[o2];
        t[o1].cnt++;

        if (l == r) {
            return;
        }

        int mid = (l + r) >> 1;

        if (x <= mid) {
            insert(t[o1].ls, t[o2].ls, l, mid, x);
        } else {
            insert(t[o1].rs, t[o2].rs, mid + 1, r, x);
        }
    }

    void insert(int x, int v) {
        insert(rt[x], rt[x - 1], 1, n, v);
    }

    int query(int o, int l, int r, int x, int y) {
        if (!o) {
            return 0;
        }
        if (x <= l && r <= y) {
            return t[o].cnt;
        }

        int mid = (l + r) >> 1;

        if (y <= mid) {
            return query(t[o].ls, l, mid, x, y);
        }
        if (x > mid) {
            return query(t[o].rs, mid + 1, r, x, y);
        }
        return query(t[o].ls, l, mid, x, y)
          + query(t[o].rs, mid + 1, r, x, y);
    }

    int query(int L, int R, int l, int r) {
        return l > r ? 0 :
          query(rt[R], 1, n, l, r) -
          query(rt[L - 1], 1, n, l, r);
    }
} segTree;

int calcA(int l, int r) {
    auto pre = --B.lower_bound({l + 1, 0});
    int ret = segTree.query(l, r, pre->first, pre->second);

    if (pre->second >= r) {
        return ret;
    }

    ret = std::min(ret, pre->second - l + 1);

    auto suf = --B.lower_bound({r + 1, 0});

    ret += segTree.query(l, r,
      pre->second + 1, suf->first - 1);
    ret += std::min(
      r - suf->first + 1,
      segTree.query(l, r, suf->first, suf->second)
    );

    return ret;
}

int calcB(int l, int r) {
    auto pre = --A.lower_bound({l + 1, 0});
    int ret = segTree.query(pre->first, pre->second, l, r);

    if (pre->second >= r) {
        return ret;
    }

    ret = std::min(ret, pre->second - l + 1);

    auto suf = --A.lower_bound({r + 1, 0});

    ret += segTree.query(
      pre->second + 1, suf->first - 1, l, r
    );
    ret += std::min(
      r - suf->first + 1,
      segTree.query(suf->first, suf->second, l, r)
    );

    return ret;
}

void updateA(int x) {
    auto it = A.lower_bound({x, x});
    auto pre = it, suf = it;
    int l = x, r = x;

    if (validA[x - 1]) {
        ans -= calcA(l = (--pre)->first, x - 1);
        A.erase(pre);
    }

    if (validA[x + 1]) {
        ans -= calcA(x + 1, r = (++suf)->second);
        A.erase(suf);
    }

    ans -= calcA(x, x);
    A.erase(it);

    ans += calcA(l, r);
    A.insert({l, r});
}

void updateB(int x) {
    auto it = B.lower_bound({x, x});
    auto pre = it, suf = it;
    int l = x, r = x;

    if (validB[x - 1]) {
        ans -= calcB(l = (--pre)->first, x - 1);
        B.erase(pre);
    }

    if (validB[x + 1]) {
        ans -= calcB(x + 1, r = (++suf)->second);
        B.erase(suf);
    }

    ans -= calcB(x, x);
    B.erase(it);

    ans += calcB(l, r);
    B.insert({l, r});
}

int main() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        pA[a[i]] = i;
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
        pB[b[i]] = i;
    }

    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }

    for (int i = 1; i <= n; i++) {
        a[i] = pB[p[a[i]]];
        ans += a[i] == i;
    }

    for (int i = 1; i <= n; i++) {
        segTree.insert(i, a[i]);

        A.insert({i, i});
        B.insert({i, i});
    }

    for (int i = 1; i <= n; i++) {
        validA[pA[i]] = validB[pB[i]] = true;

        updateA(pA[i]);
        updateB(pB[i]);

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

    return 0;
}
0