結果

問題 No.1788 Same Set
ユーザー Jeonghoo Moon
提出日時 2022-08-04 20:39:26
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 376 ms / 4,000 ms
コード長 1,370 bytes
コンパイル時間 623 ms
コンパイル使用メモリ 57,856 KB
実行使用メモリ 11,008 KB
最終ジャッジ日時 2024-09-14 17:12:49
合計ジャッジ時間 11,845 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <utility>
#include <algorithm>
using namespace std;

int n, a[200006], b[200006], lt[400006], rt[400006];

pair<int, int> tree[524288];

void update(int i, int b, int e, int l, int r, int p) {
    if (r < b || e < l) return;
    int m = (b + e) / 2;
    if (l <= b && e <= r) tree[i].second += p;
    else update(i * 2 + 1, b, m, l, r, p), update(i * 2 + 2, m + 1, e, l, r, p);
    if (tree[i].second) tree[i].first = e - b + 1;
    else if (b == e) tree[i].first = 0;
    else tree[i].first = tree[i * 2 + 1].first + tree[i * 2 + 2].first;
}

void update_rev(int x) {
    int L = min(lt[x], rt[x]) + 1;
    int R = max(lt[x], rt[x]);
    if (L <= R) update(0, 0, 262143, L, R, -1);
}

void update_for(int x) {
    int L = min(lt[x], rt[x]) + 1;
    int R = max(lt[x], rt[x]);
    if (L <= R) update(0, 0, 262143, L, R, 1);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", a + i), a[i]--;
    for (int i = 0; i < n; i++) scanf("%d", b + i), b[i]--;
    for (int i = 0; i < 400006; i++) lt[i] = rt[i] = -1;
    long long res = 0;
    for (int i = 0; i < n; i++) {
        update_rev(a[i]);
        lt[a[i]] = max(lt[a[i]], i);
        update_for(a[i]);
        update_rev(b[i]);
        rt[b[i]] = max(rt[b[i]], i);
        update_for(b[i]);
        res += i + 1 - tree[0].first;
    }
    printf("%lld", res);
}
0