Submission #71878390

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <iterator>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <utility>
#define open(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef char ch;
typedef string str;
const ll maxn=3e5+10,mod=998244353;
ll a[maxn],b[maxn],n,m,pre[maxn],nxt[maxn],sum;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++) cin>>b[i];
	sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i];
	for(int i=n;i>=1;i--) nxt[i]=nxt[i+1]+a[i];
	for(int i=1;i<=m;i++)
	{
		ll l=1,r=n,mid,temp=n;
		while(l<=r)
		{
			mid=(l+r)/2;
			if(a[mid]<b[i]) l=mid+1,temp=mid;
			else r=mid-1; 
		}
		sum=(sum+temp*b[i]-pre[temp])%mod;
		sum=(sum+nxt[temp+1]-b[i]*(n-temp))%mod;
	}
	cout<<sum;
}

Submission Info

Judge Result