Submission #71867085

---

Source Code Expand

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static final long MOD = 998244353L;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        long[] A = new long[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }

        long[] B = new long[M];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            B[i] = Long.parseLong(st.nextToken());
        }

        Arrays.sort(A);
        Arrays.sort(B);

        long[] PB = new long[M + 1];
        PB[0] = 0;
        for (int j = 0; j < M; j++) {
            PB[j + 1] = (PB[j] + B[j]) % MOD;
        }
        
        long totalSumB = PB[M];

        long totalSumS = 0;
        
        int k = 0; 
        
        for (int i = 0; i < N; i++) {
            long Ai = A[i];

            while (k < M && B[k] < Ai) {
                k++;
            }
            
            long sumB_less = PB[k];
            long termA_less = (k * Ai) % MOD;
            
            long part1 = (termA_less - sumB_less + MOD) % MOD;

            long sumB_greater = (totalSumB - sumB_less + MOD) % MOD;
            long count_greater = M - k;
            long termA_greater = (count_greater * Ai) % MOD;
            
            long part2 = (sumB_greater - termA_greater + MOD) % MOD;

            long innerSum = (part1 + part2) % MOD;

            totalSumS = (totalSumS + innerSum) % MOD;
        }

        pw.println(totalSumS);
        pw.flush();
    }
}

Submission Info

Judge Result