Submission #1987126


Source Code Expand

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

public class Main {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni();
		int[][] co = new int[n][];
		for(int i = 0;i < n;i++){
			co[i] = na(2);
		}
		Arrays.sort(co, new Comparator<int[]>() {
			public int compare(int[] a, int[] b) {
				return a[0] - b[0];
			}
		});
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = co[i][1];
		a = shrink(a);
		
		int[] lows = new int[n];
		lows[n-1] = a[n-1];
		for(int i = n-2;i >= 0;i--){
			lows[i] = Math.min(lows[i+1], a[i]);
		}
		
		int[] highs = new int[n];
		highs[0] = a[0];
		for(int i = 1;i < n;i++){
			highs[i] = Math.max(highs[i-1], a[i]);
		}
		
		long ans = 0;
		long[] dp = new long[n];
		int p = 0;
		long ts = 0;
		int mod = 1000000007;
		for(int i = 0;i < n;i++){
			while(p < i && lows[i] - highs[p] > 1){
				ts -= dp[p];
				if(ts < 0)ts += mod;
				p++;
			}
			
			dp[i] = ts + (lows[i] == 0 ? 1 : 0);
			dp[i] %= mod;
			ts += dp[i];
			if(ts >= mod)ts -= mod;
			if(highs[i] == n-1){
				ans += dp[i];
			}
		}
		out.println(ans%mod);
	}
	
	public static int lowerBound(int[] a, int v){ return lowerBound(a, 0, a.length, v); }
	public static int lowerBound(int[] a, int l, int r, int v)
	{
		if(l > r || l < 0 || r > a.length)throw new IllegalArgumentException();
		int low = l-1, high = r;
		while(high-low > 1){
			int h = high+low>>>1;
			if(a[h] >= v){
				high = h;
			}else{
				low = h;
			}
		}
		return high;
	}

	
	public static int[] shrink(int[] a) {
		int n = a.length;
		long[] b = new long[n];
		for (int i = 0; i < n; i++)
			b[i] = (long) a[i] << 32 | i;
		Arrays.sort(b);
		int[] ret = new int[n];
		int p = 0;
		for (int i = 0; i < n; i++) {
			if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0)
				p++;
			ret[(int) b[i]] = p;
		}
		return ret;
	}

	
	public static long pow(long a, long n, long mod) {
		//		a %= mod;
		long ret = 1;
		int x = 63 - Long.numberOfLeadingZeros(n);
		for (; x >= 0; x--) {
			ret = ret * ret % mod;
			if (n << 63 - x < 0)
				ret = ret * a % mod;
		}
		return ret;
	}

	
	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 E - Mr.Aoki Incubator
User uwi
Language Java8 (OpenJDK 1.8.0)
Score 1200
Code Size 5479 Byte
Status AC
Exec Time 534 ms
Memory 41592 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1200 / 1200
Status
AC × 2
AC × 36
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 204 ms 38508 KB
02.txt AC 210 ms 40376 KB
03.txt AC 486 ms 39572 KB
04.txt AC 202 ms 34540 KB
05.txt AC 271 ms 38440 KB
06.txt AC 422 ms 37160 KB
07.txt AC 294 ms 37880 KB
08.txt AC 211 ms 41592 KB
09.txt AC 363 ms 40196 KB
10.txt AC 168 ms 37256 KB
11.txt AC 182 ms 36148 KB
12.txt AC 534 ms 34704 KB
13.txt AC 179 ms 37284 KB
14.txt AC 207 ms 34908 KB
15.txt AC 387 ms 38248 KB
16.txt AC 178 ms 35364 KB
17.txt AC 202 ms 38120 KB
18.txt AC 389 ms 39476 KB
19.txt AC 213 ms 32792 KB
20.txt AC 206 ms 36224 KB
21.txt AC 394 ms 36840 KB
22.txt AC 211 ms 35952 KB
23.txt AC 207 ms 35676 KB
24.txt AC 368 ms 36172 KB
25.txt AC 181 ms 35028 KB
26.txt AC 178 ms 35416 KB
27.txt AC 378 ms 39016 KB
28.txt AC 178 ms 38124 KB
29.txt AC 238 ms 32828 KB
30.txt AC 400 ms 39360 KB
31.txt AC 71 ms 20692 KB
32.txt AC 71 ms 19028 KB
33.txt AC 72 ms 20692 KB
34.txt AC 70 ms 21204 KB
s1.txt AC 71 ms 20692 KB
s2.txt AC 70 ms 18260 KB