Submission #373911

#	Time	Username	Problem	Language	Result	Execution time	Memory
373911		jfyen	A Huge Tower (CEOI10_tower)	Java	100 / 100	573 ms	38320 KiB

tower

import java.io.FileInputStream;
import java.io.InputStream;
import java.util.*;

public class tower {

	public static void main(String[] args) throws Exception{
		FastIO sc = new FastIO(System.in);
		int N = sc.nextInt();
		int D = sc.nextInt();
		long mod = 1000000009;
		int[] blocks = new int[N];
		for (int i = 0;i<N;i++) {
			blocks[i] = sc.nextInt();
		}
		Arrays.sort(blocks);
		long[] place = new long[N];
		long[] towers = new long[N];
		towers[0] = 1;
		//place[0] = 1;
		int lower = 0;
		for (int i = 0;i<N;i++) {
			while(lower<i) {
				if(blocks[lower]+D<blocks[i])
					lower++;
				else
					break;
			}
			//System.out.println(i+" "+lower);
			place[i] = (i-lower+1)%mod;
			if (i>0)
			towers[i] = (place[i]*towers[i-1])%mod;
		}
		//System.out.println(Arrays.toString(place));
		/*for (int i = 1;i<N;i++) {
			towers[i] = (place[i]*towers[i-1])%mod;
		}*/
		System.out.println(towers[N-1]%mod);
	}

	static class FastIO {

        InputStream dis;
        byte[] buffer = new byte[1 << 17];
        int pointer = 0;

        public FastIO(String fileName) throws Exception {
            dis = new FileInputStream(fileName);
        }

        public FastIO(InputStream is) throws Exception {
            dis = is;
        }

        int nextInt() throws Exception {
            int ret = 0;

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }

            return (negative) ? -ret : ret;
        }

        long nextLong() throws Exception {
            long ret = 0;

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            boolean negative = false;
            if (b == '-') {
                negative = true;
                b = nextByte();
            }
            while (b >= '0' && b <= '9') {
                ret = 10 * ret + b - '0';
                b = nextByte();
            }

            return (negative) ? -ret : ret;
        }

        byte nextByte() throws Exception {
            if (pointer == buffer.length) {
                dis.read(buffer, 0, buffer.length);
                pointer = 0;
            }
            return buffer[pointer++];
        }

        String next() throws Exception {
            StringBuffer ret = new StringBuffer();

            byte b;
            do {
                b = nextByte();
            } while (b <= ' ');
            while (b > ' ') {
                ret.appendCodePoint(b);
                b = nextByte();
            }

            return ret.toString();
        }

    }

	
}

• 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: 5 / 5
• Subtask 14: 5 / 5
• Subtask 15: 5 / 5
• Subtask 16: 5 / 5
• Subtask 17: 5 / 5
• Subtask 18: 5 / 5
• Subtask 19: 5 / 5
• Subtask 20: 5 / 5