結果

問題 No.1788 Same Set
ユーザー chocoruskchocorusk
提出日時 2021-12-17 23:09:32
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,297 bytes
コンパイル時間 3,552 ms
コンパイル使用メモリ 192,680 KB
実行使用メモリ 19,968 KB
最終ジャッジ日時 2024-09-15 00:10:26
合計ジャッジ時間 36,195 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
16,000 KB
testcase_01 AC 11 ms
16,000 KB
testcase_02 AC 12 ms
16,128 KB
testcase_03 AC 12 ms
16,000 KB
testcase_04 AC 11 ms
16,000 KB
testcase_05 AC 12 ms
16,000 KB
testcase_06 AC 13 ms
16,000 KB
testcase_07 AC 12 ms
16,000 KB
testcase_08 AC 12 ms
16,128 KB
testcase_09 AC 12 ms
16,000 KB
testcase_10 AC 11 ms
16,128 KB
testcase_11 AC 873 ms
18,944 KB
testcase_12 AC 1,073 ms
19,584 KB
testcase_13 AC 1,137 ms
19,712 KB
testcase_14 AC 1,256 ms
19,712 KB
testcase_15 WA -
testcase_16 WA -
testcase_17 AC 1,469 ms
19,712 KB
testcase_18 WA -
testcase_19 AC 1,055 ms
19,712 KB
testcase_20 WA -
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 WA -
testcase_25 TLE -
testcase_26 WA -
testcase_27 AC 962 ms
19,072 KB
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 TLE -
testcase_32 WA -
testcase_33 WA -
testcase_34 WA -
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
権限があれば一括ダウンロードができます

ソースコード

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])-vs[i].begin();
        }
        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