제출 #1138663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1138663		QuantumPi	A Huge Tower (CEOI10_tower)	Java	65 / 100	551 ms	90912 KiB

tower

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

public class tower {
    public static void main(String[] args) throws IOException {
        BufferedReader fin = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader fin = new BufferedReader(new FileReader("C:\\Users\\AnshulRaghav\\Desktop\\USACO Problems\\Problems\\test.in"));
		    PrintWriter fout = new PrintWriter(System.out);

        StringTokenizer st = new StringTokenizer(fin.readLine());
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        ArrayList<Integer> nums = new ArrayList<>();
        st = new StringTokenizer(fin.readLine());
        for (int i=0; i<n; i++) {
            nums.add(Integer.parseInt(st.nextToken()));
        }
        Collections.sort(nums);
        //fout.println(nums);
        long ans = 1;
        for (int i=1; i<n; i++) {
            if (nums.get(i)-d <= nums.get(0)) {
                ans *= i+1;
                continue;
            }
            int low = 0;
            int high = i-1;
            while (low < high) {
                int mid = (low+high+1)/2;
                if (nums.get(i)-d > nums.get(mid)) {
                    low = mid;
                }
                else {
                    high = mid-1;
                }
            }
            ans *= i-low;
            ans %= 1000000009;
        }
        fout.println(ans);

        fin.close();
        fout.close();
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 0 / 5
• Subtask 14: 5 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5