40TLE求调
查看原帖
40TLE求调
775751
wzrysm楼主2025/7/26 12:10
//自认为复杂度良好
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[2*N],b[2*N];
int c[N];
int n;
int vis[2*N];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
unordered_map<int,int> aa; 
unordered_map<int,int> bb;
int ida[2*N]; 
int idb[2*N]; 
int asorted[2*N];
int bsorted[2*N];
int sta=1, stb=1, eda, edb; 
int main(){
    n=read();
    eda = 2*n;
    edb = 2*n;
    for(int i=1;i<=2*n;i++){
       a[i]=read();
        aa[a[i]]=i;
        asorted[i]=a[i];
    } 
    for(int i=1;i<=2*n;i++){
        b[i]=read();
        bb[b[i]]=i;
        bsorted[i]=b[i];
    }
    sort(asorted+1, asorted+2*n+1);
    sort(bsorted+1, bsorted+2*n+1);
    for(int i=1;i<=2*n;i++){
        ida[i]=aa[asorted[i]];
        idb[i]=bb[bsorted[i]];
    }
    long long mf=0, mb=0; 
    long long sf=0, sb=0; 
    for(int i=1;i<=n;i++){
        c[i]=read();
        if(c[i]==1){
            while(vis[ida[sta]]){
                sta++;
            }
            if(sta<=2*n){
                int idx=ida[sta];
                mf+=a[idx];
                mb+=b[idx];
                vis[idx]=1;
                sta++;
            }
            while(vis[ida[eda]]){
                eda--;
            }
            if(eda>=1){
                int idx=ida[eda];
                sf+=a[idx];
                sb+=b[idx];
                vis[idx]=1;
                eda--;
            }
        }else if(c[i]==2){
            while(vis[idb[stb]]){
                stb++;
            }
            if(stb<=2*n){
                int idx=idb[stb];
                mf+=a[idx];
                mb+=b[idx];
                vis[idx]=1;
                stb++;
            }
            while(vis[idb[edb]]){
                edb--;
            }
            if(edb>=1){
                int idx=idb[edb];
                sf+=a[idx];
                sb+=b[idx];
                vis[idx]=1;
                edb--;
            }
        }
    }
    cout<<sf<<" "<<sb<<"\n";
    cout<<mf<<" "<<mb<<"\n";
    return 0;
}
2025/7/26 12:10
加载中...