結果

問題 No.1300 Sum of Inversions
ユーザー DriceDrice
提出日時 2020-11-27 22:30:29
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 201 ms / 2,000 ms
コード長 2,038 bytes
コンパイル時間 398 ms
コンパイル使用メモリ 46,224 KB
実行使用メモリ 11,572 KB
最終ジャッジ日時 2023-10-09 20:33:09
合計ジャッジ時間 6,731 ms
ジャッジサーバーID
(参考情報)
judge12 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,016 KB
testcase_01 AC 2 ms
5,020 KB
testcase_02 AC 1 ms
5,032 KB
testcase_03 AC 157 ms
10,552 KB
testcase_04 AC 153 ms
10,492 KB
testcase_05 AC 121 ms
9,816 KB
testcase_06 AC 176 ms
11,048 KB
testcase_07 AC 170 ms
10,912 KB
testcase_08 AC 183 ms
11,272 KB
testcase_09 AC 181 ms
11,196 KB
testcase_10 AC 98 ms
9,236 KB
testcase_11 AC 96 ms
9,280 KB
testcase_12 AC 150 ms
10,540 KB
testcase_13 AC 146 ms
10,380 KB
testcase_14 AC 201 ms
11,464 KB
testcase_15 AC 185 ms
11,160 KB
testcase_16 AC 166 ms
10,648 KB
testcase_17 AC 94 ms
9,164 KB
testcase_18 AC 110 ms
9,528 KB
testcase_19 AC 132 ms
10,052 KB
testcase_20 AC 135 ms
10,144 KB
testcase_21 AC 136 ms
10,136 KB
testcase_22 AC 123 ms
9,820 KB
testcase_23 AC 177 ms
11,008 KB
testcase_24 AC 125 ms
9,900 KB
testcase_25 AC 107 ms
9,464 KB
testcase_26 AC 108 ms
9,384 KB
testcase_27 AC 121 ms
9,728 KB
testcase_28 AC 190 ms
11,252 KB
testcase_29 AC 138 ms
10,096 KB
testcase_30 AC 184 ms
11,124 KB
testcase_31 AC 125 ms
9,740 KB
testcase_32 AC 129 ms
9,928 KB
testcase_33 AC 67 ms
10,272 KB
testcase_34 AC 80 ms
10,228 KB
testcase_35 AC 117 ms
11,556 KB
testcase_36 AC 123 ms
11,572 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include<cstdio>
#include<algorithm>
const long long mod = 998244353;
//bit[0]: cnt, bit[1]: sum
long long bit[2][200005];
long long a[200005];
long long b[200005];
long long c[200005]; // count
int map[200005];

long long ask(int p,long long bit[]){
    long long res = 0;
    while(p!=0){
        res += bit[p];
        if(res>=mod) res -= mod;
        p -= p&-p;
    }
    return res;
}

void change(int p, long long v, int n, long long bit[]){
    while(p<=n){
        bit[p] = (bit[p]+v)%mod;
        p += p&-p;
    }
}

int preWork(int n){
    std::sort(map+1,map+1+n);
    int  p = 1, size = 0;
    while(p<=n){
        int np = p;
        while(np+1<=n && map[np+1]==map[p]) np++;
        map[++size] = map[p];
        p = np+1;
    }
    return size;
}

int getId(int u,int n){
    int L = 1, R = n;
    int res = -1;
    while(L<=R){
        int M = (L+R)/2;
        if(map[M]<=u){
            res = M;
            L = M+1;
        }
        else R = M-1;
    }
    return res;
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){ 
        scanf("%lld",&a[i]);
        map[i] = a[i];
    }
    int size = preWork(n);
    for(int i = n; i >= 1; i--){
        int upper = getId(a[i]-1,size);
        if(upper!=-1){
            long long cnt = ask(upper,bit[0]);
            long long sum = ask(upper,bit[1]);
            b[i] = (cnt*a[i]%mod+sum)%mod;
            c[i] = cnt;
        }
        int u = getId(a[i],size);
        change(u,1,n,bit[0]);
        change(u,a[i],n,bit[1]);
    }
    for(int i = 1; i <= n; i++) bit[0][i] = bit[1][i] = 0;
    long long ans = 0;
    for(int i = n; i >= 1; i--){
        int upper = getId(a[i]-1,size);
        if(upper!=-1){
            long long cnt = ask(upper,bit[0]);
            long long sum = ask(upper,bit[1]);
            long long cur = (cnt*a[i]%mod+sum)%mod;
            ans = (ans+cur)%mod;
        }
        int u = getId(a[i],size);
        change(u,c[i],n,bit[0]);
        change(u,b[i],n,bit[1]);
    }
    printf("%lld\n",ans);
    return 0;
}
0