結果

問題 No.1788 Same Set
ユーザー chocoruskchocorusk
提出日時 2021-12-17 22:52:29
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 3,777 bytes
コンパイル時間 3,654 ms
コンパイル使用メモリ 193,772 KB
実行使用メモリ 14,008 KB
最終ジャッジ日時 2024-09-14 23:50:54
合計ジャッジ時間 17,119 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
6,784 KB
testcase_01 AC 3 ms
6,784 KB
testcase_02 AC 3 ms
6,784 KB
testcase_03 AC 3 ms
6,784 KB
testcase_04 AC 4 ms
6,784 KB
testcase_05 AC 4 ms
6,912 KB
testcase_06 AC 5 ms
6,784 KB
testcase_07 AC 4 ms
6,784 KB
testcase_08 AC 4 ms
6,784 KB
testcase_09 AC 4 ms
6,784 KB
testcase_10 AC 3 ms
6,912 KB
testcase_11 AC 876 ms
9,216 KB
testcase_12 AC 1,168 ms
9,824 KB
testcase_13 AC 1,267 ms
9,984 KB
testcase_14 AC 1,428 ms
9,828 KB
testcase_15 WA -
testcase_16 TLE -
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];
int pra[400040], prb[400040];
int v[200020];
const int sq=500;
int s[5000];
vector<int> 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];
    }
    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, int 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=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;
    };
    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