結果

問題 No.1788 Same Set
ユーザー chocoruskchocorusk
提出日時 2021-12-17 22:03:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,635 bytes
コンパイル時間 3,351 ms
コンパイル使用メモリ 187,556 KB
最終ジャッジ日時 2025-01-27 02:19:40
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 9 WA * 7 TLE * 20
権限があれば一括ダウンロードができます

ソースコード

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(334334);
int pra[400040], prb[400040];
ull z[400040];
ull v[200020];
const int sq=500;
ull s[5000];
vector<ull> vs[5000];
bool sorted[5000];
int main()
{
    cin>>n;
    for(int i=0; i<n; i++){
        //a[i]=i%(n/2)+1;
        cin>>a[i];
    }
    for(int i=0; i<n; i++){
        //b[i]=i%(n/2)+1;
        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);
        sorted[i/sq]=1;
    }
    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;
            sorted[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;
        sorted[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;
        sorted[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; i<r1; i++){
            if(!sorted[i]){
                sorted[i]=1;
                sort(vs[i].begin(), vs[i].end());
            }
            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] に z[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