結果

問題 No.1788 Same Set
ユーザー Jeonghoo MoonJeonghoo Moon
提出日時 2022-08-04 20:39:26
言語 C++23
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
6,272 KB
testcase_01 AC 4 ms
6,400 KB
testcase_02 AC 5 ms
6,144 KB
testcase_03 AC 4 ms
6,272 KB
testcase_04 AC 4 ms
6,272 KB
testcase_05 AC 4 ms
6,400 KB
testcase_06 AC 4 ms
6,272 KB
testcase_07 AC 4 ms
6,272 KB
testcase_08 AC 4 ms
6,272 KB
testcase_09 AC 4 ms
6,272 KB
testcase_10 AC 4 ms
6,272 KB
testcase_11 AC 117 ms
10,880 KB
testcase_12 AC 171 ms
10,880 KB
testcase_13 AC 178 ms
10,880 KB
testcase_14 AC 223 ms
10,880 KB
testcase_15 AC 278 ms
10,880 KB
testcase_16 AC 328 ms
10,880 KB
testcase_17 AC 217 ms
10,880 KB
testcase_18 AC 279 ms
10,880 KB
testcase_19 AC 140 ms
10,752 KB
testcase_20 AC 169 ms
11,008 KB
testcase_21 AC 290 ms
11,008 KB
testcase_22 AC 311 ms
11,008 KB
testcase_23 AC 279 ms
10,880 KB
testcase_24 AC 323 ms
10,752 KB
testcase_25 AC 368 ms
10,880 KB
testcase_26 AC 364 ms
10,880 KB
testcase_27 AC 217 ms
10,880 KB
testcase_28 AC 376 ms
10,880 KB
testcase_29 AC 329 ms
10,880 KB
testcase_30 AC 218 ms
10,880 KB
testcase_31 AC 347 ms
10,880 KB
testcase_32 AC 277 ms
10,880 KB
testcase_33 AC 299 ms
10,880 KB
testcase_34 AC 323 ms
10,880 KB
testcase_35 AC 316 ms
10,880 KB
testcase_36 AC 321 ms
10,880 KB
testcase_37 AC 320 ms
11,008 KB
testcase_38 AC 311 ms
10,880 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