結果

問題 No.1788 Same Set
ユーザー chocoruskchocorusk
提出日時 2021-12-17 00:55:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 3,328 bytes
コンパイル時間 3,684 ms
コンパイル使用メモリ 195,220 KB
実行使用メモリ 22,252 KB
最終ジャッジ日時 2024-09-14 00:55:41
合計ジャッジ時間 20,538 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
11,848 KB
testcase_01 AC 8 ms
11,836 KB
testcase_02 AC 8 ms
11,840 KB
testcase_03 AC 7 ms
9,832 KB
testcase_04 AC 7 ms
9,832 KB
testcase_05 AC 7 ms
9,908 KB
testcase_06 AC 10 ms
11,840 KB
testcase_07 AC 9 ms
10,064 KB
testcase_08 AC 9 ms
10,192 KB
testcase_09 AC 7 ms
11,836 KB
testcase_10 AC 7 ms
11,844 KB
testcase_11 AC 2,492 ms
15,752 KB
testcase_12 AC 2,548 ms
15,588 KB
testcase_13 AC 2,581 ms
15,624 KB
testcase_14 AC 2,747 ms
15,708 KB
testcase_15 TLE -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#include <atcoder/all>
#define popcount __builtin_popcount
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
using mint=modint1000000007;
using ull=unsigned long long;
int n;
int a[200020], b[200020];
mt19937_64 mt(334);
int pra[400040], prb[400040];
ull z[400040];
ull v[200020];
const int sq=300;
ull s[5000];
vector<ull> vs[5000];
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        cin>>a[i];
    }
    for(int i=0; i<n; i++){
        cin>>b[i];
    }
    for(int i=1; i<=400000; i++) z[i]=mt();
    fill(pra, pra+400001, -1);
    fill(prb, prb+400001, -1);
    ll ans=0;
    for(int i=0; i<n; i++){
        vs[i/sq].push_back(0);
    }
    auto add=[&](int l, int r, ull x){//[l,r]
        int l1=l/sq, r1=r/sq;
        if(l1==r1){
            for(int i=0; i<vs[l1].size(); i++){
                if(i>=l-sq*l1 && i<=r-sq*r1){
                    v[i+sq*l1]=(x^v[i+sq*l1]^s[l1]);
                    vs[l1][i]=v[i+sq*l1];
                }else{
                    v[i+sq*l1]=(v[i+sq*l1]^s[l1]);
                    vs[l1][i]=v[i+sq*l1];
                }
            }
            s[l1]=0;
            sort(vs[l1].begin(), vs[l1].end());
            return;
        }
        for(int i=0; i<vs[l1].size(); i++){
            if(i>=l-sq*l1){
                v[i+sq*l1]=(x^v[i+sq*l1]^s[l1]);
                vs[l1][i]=v[i+sq*l1];
            }else{
                v[i+sq*l1]=(v[i+sq*l1]^s[l1]);
                vs[l1][i]=v[i+sq*l1];
            }
        }
        s[l1]=0;
        sort(vs[l1].begin(), vs[l1].end());
        for(int i=0; i<vs[r1].size(); i++){
            if(i<=r-sq*r1){
                v[i+sq*r1]=(x^v[i+sq*r1]^s[r1]);
                vs[r1][i]=v[i+sq*r1];
            }else{
                v[i+sq*r1]=(v[i+sq*r1]^s[r1]);
                vs[r1][i]=v[i+sq*r1];
            }
        }
        s[r1]=0;
        sort(vs[r1].begin(), vs[r1].end());
        for(int i=l1+1; i<r1; i++) s[i]^=x;
    };
    auto count=[&](int l, int r){
        int l1=l/sq, r1=r/sq;
        int res=0;
        if(l1==r1){
            for(int i=l; i<=r; i++){
                if(v[i]==s[i]) res++;
            }
            return res;
        }
        for(int i=l; i<(l1+1)*sq && i<n; i++){
            if(v[i]==s[i]) res++;
        }
        for(int i=r1*sq; i<=r; i++){
            if(v[i]==s[i]) res++;
        }
        for(int i=l1+1; i<r1; i++){
            res+=upper_bound(vs[i].begin(), vs[i].end(), s[i])-lower_bound(vs[i].begin(), vs[i].end(), s[i]);
        }
        return res;
    };
    for(int i=0; i<n; i++){
        // [pra[a[i]]+1, i] に z[a[i]] を xor
        // [prb[b[i]]+1, i] に v[b[i]] を xor
        // 0の個数？
        add(pra[a[i]]+1, i, z[a[i]]);
        add(prb[b[i]]+1, i, z[b[i]]);
        ans+=count(0, i);
        pra[a[i]]=i, prb[b[i]]=i;
    }
    cout<<ans<<endl;
    return 0;
}
0