Submission #171543


Source Code Expand

Copy
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int[] a = na(n);
		int mod = 1000000007;
		long ret = 1;
		for(int i = 0;i < n;){
			if(i == n-1)break;
			if(a[i] != -1){
				int j;
				for(j = i+1;j < n && a[j] == -1;j++);
				long num = 1, den = 1;
				for(int k = 1;k <= j-i-1;k++){
					num = num * (a[j]-a[i]+j-i-1-k+1) % mod;
					den = den * k % mod;
				}
				ret = ret * num % mod * invl(den, mod) % mod;
				i = j;
			}
		}
		out.println(ret);
	}
	
	public static long invl(long a, long mod)
	{
		long b = mod;
		long p = 1, q = 0;
		while(b > 0){
			long c = a / b;
			long d;
			d = a; a = b; b = d % b;
			d = p; p = q; q = d - c * q;
		}
		return p < 0 ? p + mod : p;
	}
	
	public static void main(String[] args) throws Exception
	{
		long S = System.currentTimeMillis();
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
		long G = System.currentTimeMillis();
		tr(G-S+"ms");
	}
	
	private static boolean eof()
	{
		if(lenbuf == -1)return true;
		int lptr = ptrbuf;
		while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
		
		try {
			is.mark(1000);
			while(true){
				int b = is.read();
				if(b == -1){
					is.reset();
					return true;
				}else if(!isSpaceChar(b)){
					is.reset();
					return false;
				}
			}
		} catch (IOException e) {
			return true;
		}
	}
	
	private static byte[] inbuf = new byte[1024];
	static int lenbuf = 0, ptrbuf = 0;
	
	private static int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
//	private static boolean isSpaceChar(int c) { return !(c >= 32 && c <= 126); }
	private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private static double nd() { return Double.parseDouble(ns()); }
	private static char nc() { return (char)skip(); }
	
	private static String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private static char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private static char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private static int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private static int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}

Submission Info

Submission Time
Task C - タコヤ木
User uwi
Language Java (OpenJDK 1.7.0)
Score 100
Code Size 4108 Byte
Status AC
Exec Time 446 ms
Memory 20592 KB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3
Score / Max Score 0 / 0 50 / 50 30 / 30 20 / 20
Status
AC × 3
AC × 14
AC × 26
AC × 36
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt
Subtask2 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt
Subtask3 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask3_01.txt, subtask3_02.txt, subtask3_03.txt, subtask3_04.txt, subtask3_05.txt, subtask3_06.txt, subtask3_07.txt, subtask3_08.txt, subtask3_09.txt, subtask3_10.txt, subtask3_11.txt, subtask3_12.txt
Case Name Status Exec Time Memory
sample_01.txt AC 415 ms 20156 KB
sample_02.txt AC 398 ms 20144 KB
sample_03.txt AC 393 ms 20152 KB
subtask1_01.txt AC 386 ms 20152 KB
subtask1_02.txt AC 397 ms 20148 KB
subtask1_03.txt AC 400 ms 20136 KB
subtask1_04.txt AC 409 ms 20108 KB
subtask1_05.txt AC 438 ms 20196 KB
subtask1_06.txt AC 406 ms 20152 KB
subtask1_07.txt AC 410 ms 20156 KB
subtask1_08.txt AC 416 ms 20156 KB
subtask1_09.txt AC 407 ms 20156 KB
subtask1_10.txt AC 423 ms 20120 KB
subtask1_11.txt AC 400 ms 20156 KB
subtask1_12.txt AC 397 ms 20108 KB
subtask2_01.txt AC 391 ms 20148 KB
subtask2_02.txt AC 408 ms 20220 KB
subtask2_03.txt AC 422 ms 20192 KB
subtask2_04.txt AC 416 ms 20132 KB
subtask2_05.txt AC 418 ms 20128 KB
subtask2_06.txt AC 416 ms 20116 KB
subtask2_07.txt AC 412 ms 20152 KB
subtask2_08.txt AC 405 ms 20152 KB
subtask2_09.txt AC 416 ms 20152 KB
subtask2_10.txt AC 424 ms 20132 KB
subtask2_11.txt AC 423 ms 20136 KB
subtask2_12.txt AC 417 ms 20152 KB
subtask3_01.txt AC 440 ms 20124 KB
subtask3_02.txt AC 409 ms 20152 KB
subtask3_03.txt AC 408 ms 20188 KB
subtask3_04.txt AC 426 ms 20444 KB
subtask3_05.txt AC 400 ms 20188 KB
subtask3_06.txt AC 402 ms 20152 KB
subtask3_07.txt AC 431 ms 20112 KB
subtask3_08.txt AC 422 ms 20592 KB
subtask3_09.txt AC 422 ms 20156 KB
subtask3_10.txt AC 440 ms 20464 KB
subtask3_11.txt AC 427 ms 20232 KB
subtask3_12.txt AC 446 ms 20576 KB