Submission #71855919

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 3e5+5;
const int MOD = 998244353;
int n, m, a[MAXN], b[MAXN], qian[MAXN], hou[MAXN];


signed main()
{
    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);
    sort(b+1, b+m+1);
    for (int i=1; i<=m; i++) qian[i] = qian[i-1]+b[i];
    for (int i=m; i>=1; i--) hou[i] = hou[i+1]+b[i];
    int now = 1, ans=0; // b中[1, now-1]的部分比ai小，[now, n]的部分比ai大
    // for (int i=1; i<=n; i++) cout << a[i] << " ";
    // cout << endl;
    // for (int i=1; i<=m; i++) cout << b[i] << " ";
    // cout << endl;
    for (int i=1; i<=n; i++)
    {
        while (b[now]<a[i] && now<=m) now++;
        ans += a[i]*(now-1)-qian[now-1];
        // cout << "*"<< ans << endl;
        ans += hou[now]-a[i]*(m-now+1);
        ans %= MOD;
        // cout << ans << endl;
    }
    cout << ans;

    return 0;
}

Submission Info

Submission Time
Task D - Sum of Differences
User nxzwcry
Language C++23 (GCC 15.2.0)
Score 400
Code Size 1004 Byte
Status AC
Exec Time 195 ms
Memory 13028 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 32
Set Name Test Cases
Sample 00-sample-01.txt, 00-sample-02.txt
All 00-sample-01.txt, 00-sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt
Case Name Status Exec Time Memory
00-sample-01.txt AC 1 ms 3504 KiB
00-sample-02.txt AC 1 ms 3660 KiB
01-01.txt AC 4 ms 3840 KiB
01-02.txt AC 4 ms 3616 KiB
01-03.txt AC 5 ms 3652 KiB
01-04.txt AC 5 ms 3848 KiB
01-05.txt AC 5 ms 3652 KiB
01-06.txt AC 4 ms 3784 KiB
01-07.txt AC 6 ms 3624 KiB
01-08.txt AC 5 ms 3828 KiB
01-09.txt AC 5 ms 3840 KiB
01-10.txt AC 4 ms 3848 KiB
01-11.txt AC 4 ms 3828 KiB
01-12.txt AC 4 ms 3848 KiB
01-13.txt AC 5 ms 3756 KiB
01-14.txt AC 5 ms 3848 KiB
01-15.txt AC 1 ms 3600 KiB
01-16.txt AC 1 ms 3584 KiB
01-17.txt AC 148 ms 11372 KiB
01-18.txt AC 150 ms 9984 KiB
01-19.txt AC 99 ms 10560 KiB
01-20.txt AC 98 ms 6080 KiB
01-21.txt AC 195 ms 12696 KiB
01-22.txt AC 164 ms 12992 KiB
01-23.txt AC 169 ms 13028 KiB
01-24.txt AC 186 ms 12856 KiB
01-25.txt AC 182 ms 12824 KiB
01-26.txt AC 151 ms 12756 KiB
01-27.txt AC 138 ms 9792 KiB
01-28.txt AC 146 ms 10752 KiB
01-29.txt AC 123 ms 10544 KiB
01-30.txt AC 151 ms 11924 KiB