結果

問題 No.1788 Same Set
コンテスト
ユーザー vjudge1
提出日時 2025-10-16 15:57:39
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 365 ms / 4,000 ms
コード長 1,370 bytes
コンパイル時間 482 ms
コンパイル使用メモリ 59,964 KB
実行使用メモリ 9,892 KB
最終ジャッジ日時 2025-10-16 15:57:50
合計ジャッジ時間 9,998 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:33:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   33 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
main.cpp:34:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   34 |     for (int i = 0; i < n; i++) scanf("%d", a + i), a[i]--;
      |                                 ~~~~~^~~~~~~~~~~~~
main.cpp:35:38: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   35 |     for (int i = 0; i < n; i++) scanf("%d", b + i), b[i]--;
      |                                 ~~~~~^~~~~~~~~~~~~

ソースコード

diff #
raw source code 

#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