当前位置: 首页 > 工具软件 > Gorillas > 使用案例 >

1793D Moscow Gorillas

俞衡虑
2023-12-01

Moscow Gorillas
考虑区间不包含的最小的数
对于1 不包含1的区间都可取
对于2 在包含1的基础上不包含2 以此类推

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    vector<int> pos1(n+1),pos2(n+1);
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        pos1[x]=i;
    }
    for (int i=1;i<=n;i++){
        int x;
        cin>>x;
        pos2[x]=i;
    }

    for (int i=1;i<=n;i++){
        if (pos2[i]<pos1[i]){
            swap(pos1[i],pos2[i]);
        }
    }

    int l=pos1[1],r=pos2[1];
    // cout<<l<<" "<<r<<"\n";
    ll ans=1LL*(l-1)*l/2+1LL*(n-r)*(1+n-r)/2+1LL*(r-l)*(r-l-1)/2;
    for (int i=2;i<=n;i++){
        if (pos2[i]>r&&pos1[i]<l){
            ans+=1LL*(l-pos1[i])*(pos2[i]-r);
            l=pos1[i];
            r=pos2[i];
        }else if (pos2[i]<l){
            ans+=1LL*(l-pos2[i])*(n-r+1);
            l=pos1[i];
        }else if (pos1[i]>r){
            ans+=1LL*(pos1[i]-r)*l;
            r=pos2[i];
        }
        else{
            l=min(l,pos1[i]);
            r=max(r,pos2[i]);
        }
    }

    cout<<ans+1;
    return 0;
}
 类似资料:

相关阅读

相关文章

相关问答