后面十个点WA 大佬帮忙看看 谢谢

P1908 逆序对

DOs__lx @ 2020-02-23 13:05:49

只有50分 QWQ

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define re register
const int M=5e5+5;
int a[M],r[M],n;
long long ans;
namespace fir{
    inline int read(){
        int s=0,w=1;
        char c=getchar();
        while(c>'9'||c<'0'){
            if(c=='-') w=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9'){
            s=(s<<3)+(s<<1)+(c^48);
            c=getchar();
        }
        return s*w;
    }
    inline void write(int a){
        int tot=abs(a);
        if(a<0) putchar('-');
        int cnt=0;
        char c[M];
        while(tot>0){
            c[cnt++]=tot%10+'0';
            tot/=10;
        }
        while(cnt>0) putchar(c[--cnt]);
    }
}
namespace solve{
    inline void msort(int s,int t){
        if(s==t) return;
        int mid=s+t>>1;
        msort(s,mid);
        msort(mid+1,t);
        int i=s;
        int j=mid+1;
        int k=s;
        while(i<=mid&&j<=t){
            if(a[i]<=a[j]){
                r[k]=a[i];
                k++;
                i++;
            }
            else{
                r[k]=a[j];
                k++;
                j++;
                ans+=(long long)mid-i+1;
            }
        }
        while(i<=mid){
            r[k]=a[i];
            k++;
            i++;
        }
        while(j<=t){
            r[k]=a[j];
            k++;
            j++;
        }
        for(int i=s;i<=t;++i) a[i]=r[i];
    }
}
int main(){
    n=fir::read();
    for(int i=1;i<=n;++i) a[i]=fir::read();
    solve::msort(1,n);
    fir::write(ans);
    return 0;
} 

by DOs__lx @ 2020-02-23 13:24:16

@WYXkk


by DOs__lx @ 2020-02-23 13:24:29

@我不是箭毒蛙


by DOs__lx @ 2020-02-23 13:24:45

@YCE3216037


by DOs__lx @ 2020-02-23 13:25:00

@Alpha


by DOs__lx @ 2020-02-23 13:25:23

蟹蟹了 各位大佬


上一页 |