Submission #71849072

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll MOD = 998244353;

ll mult(ll a, ll b){
    return ((a % MOD) * (b % MOD)) % MOD;
}

ll add(ll a, ll b){
    return ((a % MOD) + (b % MOD)) % MOD;
}

ll subt(ll a, ll b){
    return ((a % MOD) - (b % MOD) + MOD) % MOD;
}

ll binpow(ll a, ll b){
    if(b == 0) return 1;
    if(b & 1){
        return mult(a, binpow(a, b-1));
    }

    ll tmp = binpow(a, b/2);
    return mult(tmp, tmp);
}

ll inv(ll x){
    return binpow(x, MOD-2);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin>>n>>m;

    ll a[n+5], b[m+5];
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=m; i++) cin>>b[i];

    sort(a+1, a+1+n);
    sort(b+1, b+1+m);

    ll pre[m+5];
    pre[0] = 0;
    for(int i=1; i<=m; i++){
        pre[i] = add(pre[i-1], b[i]);
    }

    ll ans = 0;
    int idx = 0;
    for(int i=1; i<=n; i++){
        while(idx + 1 <= m && b[idx + 1] <= a[i]) idx++;
        // cout<<i<<" "<<idx<<endl;
        ll left = idx;
        ll right = m-idx;
        // cout<<subt(mult(a[i], left), pre[left])<<' '<<subt(subt(pre[m], pre[left]), mult(a[i], right))<<endl;
        ans = add(ans, subt(mult(a[i], left), pre[left]));
        ans = add(ans, subt(subt(pre[m], pre[left]), mult(a[i], right)));
        // cout<<endl;
    }
    cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result