結果

問題 No.1788 Same Set
ユーザー Jeonghoo MoonJeonghoo Moon
提出日時 2022-08-04 20:39:26
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 370 ms / 4,000 ms
コード長 1,370 bytes
コンパイル時間 451 ms
コンパイル使用メモリ 58,644 KB
実行使用メモリ 10,876 KB
最終ジャッジ日時 2023-10-12 18:46:34
合計ジャッジ時間 12,405 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
7,112 KB
testcase_01 AC 3 ms
7,176 KB
testcase_02 AC 2 ms
7,172 KB
testcase_03 AC 3 ms
7,164 KB
testcase_04 AC 2 ms
7,116 KB
testcase_05 AC 3 ms
7,116 KB
testcase_06 AC 3 ms
7,172 KB
testcase_07 AC 3 ms
7,160 KB
testcase_08 AC 2 ms
7,172 KB
testcase_09 AC 3 ms
7,040 KB
testcase_10 AC 2 ms
7,052 KB
testcase_11 AC 115 ms
10,792 KB
testcase_12 AC 158 ms
10,808 KB
testcase_13 AC 177 ms
10,812 KB
testcase_14 AC 220 ms
10,812 KB
testcase_15 AC 274 ms
10,856 KB
testcase_16 AC 323 ms
10,824 KB
testcase_17 AC 211 ms
10,748 KB
testcase_18 AC 272 ms
10,808 KB
testcase_19 AC 130 ms
10,856 KB
testcase_20 AC 163 ms
10,848 KB
testcase_21 AC 287 ms
10,868 KB
testcase_22 AC 312 ms
10,848 KB
testcase_23 AC 278 ms
10,844 KB
testcase_24 AC 312 ms
10,856 KB
testcase_25 AC 363 ms
10,856 KB
testcase_26 AC 351 ms
10,840 KB
testcase_27 AC 210 ms
10,856 KB
testcase_28 AC 370 ms
10,804 KB
testcase_29 AC 321 ms
10,872 KB
testcase_30 AC 209 ms
10,796 KB
testcase_31 AC 342 ms
10,852 KB
testcase_32 AC 271 ms
10,872 KB
testcase_33 AC 289 ms
10,876 KB
testcase_34 AC 314 ms
10,740 KB
testcase_35 AC 308 ms
10,808 KB
testcase_36 AC 311 ms
10,736 KB
testcase_37 AC 320 ms
10,868 KB
testcase_38 AC 305 ms
10,800 KB
権限があれば一括ダウンロードができます

ソースコード

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