提出 #70447345

---

ソースコード 拡げる

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int N = Integer.parseInt(st.nextToken());
        long M = Long.parseLong(st.nextToken());
        int C = 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());
        }
        
        Arrays.sort(A);
        
        ArrayList<Long> pos = new ArrayList<>();
        ArrayList<Integer> cnt = new ArrayList<>();
        
        pos.add(A[0]);
        int cur = 1;
        
        for (int i = 1; i < N; i++) {
            if (A[i] == A[i-1]) {
                cur++;
            } else {
                cnt.add(cur);
                pos.add(A[i]);
                cur = 1;
            }
        }
        cnt.add(cur);
        
        int K = pos.size();
        int[] pref = new int[2 * K + 1];
        
        for (int i = 0; i < K; i++) {
            pref[i + 1] = pref[i] + cnt.get(i);
        }
        for (int i = K; i < 2 * K; i++) {
            pref[i + 1] = pref[i] + cnt.get(i - K);
        }
        
        long ans = 0;
        
        for (int i = 0; i < K; i++) {
            long sp = pos.get(i);
            long np = pos.get((i + 1) % K);
            
            long len = (np > sp) ? (np - sp) : (M - sp + np);
            
            int meet = 0;
            int low = i + 1;
            int high = i + K;
            int idx = i + K;
            
            while (low <= high) {
                int mid = (low + high) / 2;
                if (pref[mid + 1] - pref[i + 1] >= C) {
                    idx = mid;
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            
            meet = pref[idx + 1] - pref[i + 1];
            ans += (long) meet * len;
        }
        
        System.out.println(ans);
    }
}

提出情報

ジャッジ結果