結果

問題 No.1788 Same Set
ユーザー chocorusk
提出日時 2021-12-17 23:17:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,332 bytes
コンパイル時間 3,425 ms
コンパイル使用メモリ 186,036 KB
最終ジャッジ日時 2025-01-27 02:43:00
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 16 WA * 4 TLE * 16
権限があれば一括ダウンロードができます

ソースコード

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[400040], b[400040];
int pra[400040], prb[400040];
int v[400040];
const int sq=300;
int s[400040];
vector<int> vs[400040];
bool sorted[400040];
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];
    }
    fill(pra, pra+400040, -1);
    fill(prb, prb+400040, -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, int x){//[l,r]
        int l1=l/sq, r1=r/sq;
        if(l1==r1){
            for(int i=l1*sq; i<(l1+1)*sq && i<n; i++){
                v[i]+=s[l1];
                if(l<=i && i<=r) v[i]+=x;
                vs[l1][i-l1*sq]=v[i];
            }
            s[l1]=0;
            sorted[l1]=0;
            return;
        }
        for(int i=l1*sq; i<(l1+1)*sq && i<n; i++){
            v[i]+=s[l1];
            if(l<=i) v[i]+=x;
            vs[l1][i-l1*sq]=v[i];
        }
        s[l1]=0;
        sorted[l1]=0;
        //sort(vs[l1].begin(), vs[l1].end());
        for(int i=r1*sq; i<(r1+1)*sq && i<n; i++){
            v[i]+=s[i];
            if(i<=r) v[i]+=x;
            vs[r1][i-sq*r1]=v[i];
        }
        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=r1*sq; i<=r; i++){
            if(v[i]==-s[i]) res++;
        }
        for(int i=l1; i<r1; i++){
            //if(s[i]) continue;
            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;
    };
    int l1, r1;
    for(int i=0; i<n; i++){
        l1=min(pra[a[i]], prb[a[i]])+1, r1=max(pra[a[i]], prb[a[i]]);
        if(l1<=r1) add(l1, r1, -1);
        if(a[i]!=b[i]){
            l1=min(pra[b[i]], prb[b[i]])+1, r1=max(pra[b[i]], prb[b[i]]);
            if(l1<=r1) add(l1, r1, -1);
        }
        pra[a[i]]=i, prb[b[i]]=i;
        l1=min(pra[a[i]], prb[a[i]])+1, r1=max(pra[a[i]], prb[a[i]]);
        if(l1<=r1) add(l1, r1, 1);
        if(a[i]!=b[i]){
            l1=min(pra[b[i]], prb[b[i]])+1, r1=max(pra[b[i]], prb[b[i]]);
            if(l1<=r1) add(l1, r1, 1);
        }
        ans+=count(0, i);
    }
    cout<<ans<<endl;
    return 0;
}
0