제출 #713680

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
713680		hex	A Huge Tower (CEOI10_tower)	Java	0 / 100	300 ms	42512 KiB

tower

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

public class tower {
	static final long MOD = (long) (1e9 + 9);

	public static void main (String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(reader.readLine());
		int N = Integer.parseInt(st.nextToken());
		int diff = Integer.parseInt(st.nextToken());
		int[] sizes = new int[N];
		st = new StringTokenizer(reader.readLine());
		for (int n = 0; n < N; n++) {
			sizes[n] = Integer.parseInt(st.nextToken());
		}
		int lt = 0;
		int rt = 0;
		long len;
		int ans = 1;
		while (lt < N) {
			while (rt < N - 1 && sizes[rt + 1] <= sizes[lt] + diff) rt++;
			len = rt - lt + 1;
			ans = (int) ((ans * len) % MOD);
			lt++;
		}
		out.println(ans);
		out.close();
	}
}
//Check N = 1.
//Check for needed longs.
//Use Long.parseLong() instead of Integer.parseInt().
//Use Long.MAX_VALUE instead of Integer.MAX_VALUE.
//Use an int array of ids instead of a boolean array of visited nodes during DFS.
//Declare a class variable instead of a method parameter, as passing by value could result in a TLE.

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 5
• Subtask 4: 0 / 5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 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