結果

問題 No.8016 unordered_mapなるたけ落とすマン
ユーザー 37zigen
提出日時 2016-05-22 01:23:57
言語 Java
(openjdk 23)
結果
MLE  
実行時間 -
コード長 2,605 bytes
コンパイル時間 2,441 ms
コンパイル使用メモリ 81,072 KB
実行使用メモリ 83,676 KB
最終ジャッジ日時 2024-10-07 06:07:54
合計ジャッジ時間 49,500 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 3
other TLE * 34 MLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
public class Main{
	public static void main(String[] args){
		new Main().solve();
	}
	void solve(){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		long[] d=new long[n];
		for(int i=0;i<n;i++){
			d[i]=sc.nextLong();
		}
		Arrays.sort(d);
		for(int i=0;i<m;i++){
			long a=sc.nextLong();
			int min=0;int max=n-1;
			if(a<d[min]||a>d[max]){
				System.out.print(0+(i==m-1?"\n":" "));
			}else{
				System.out.print(upper_bound(d,a)-lower_bound(d, a)+(i==m-1?"\n":" "));
			}
		}
	}
	//昇順の配列に対して使える。
	//upper_boundはaより大きい数値の場所を示す。配列の最後の位置がaの時は、d.lengthを返す。
	//aが存在しないときは-Integer.MAX_VALUEを返す
	//lower_boundはaの場所を返す。aが複数ある時は一番最初のaの場所を返す。
	//aが存在しないときは-Integer.MAX_VALUEを返す。
	int upper_bound(long[] d,long a){
		int min=0;
		int max=d.length;
		for(int i=0;Math.pow(2, i)<d.length+5;i++){
			int mid=(max+min)/2;
			if(d[mid]>a){
				max=mid;
			}else{
				min=mid;
			}
			if(max==min+1&&d[min]==a)
				return max;
		}
		return -Integer.MAX_VALUE/4;
	}
	int lower_bound(long[] d,long a){
		int min=-1;
		int max=d.length-1;
		for(int i=0;Math.pow(2, i)<d.length+5;i++){
			int mid=(max+min)/2;
			if(d[mid]>=a){
				max=mid;
			}else{
				min=mid;
			}
			if(d[max]==a&&min+1==max)
				return max;
		}
		return -Integer.MAX_VALUE/4;
	}
	private static class Scanner{
		BufferedReader br;
		Iterator<String> it;
		Scanner(InputStream in){
			br=new BufferedReader(new InputStreamReader(in));
		}
		String next()throws RuntimeException{
			try{
				if(it==null||!it.hasNext())
					it=Arrays.asList(br.readLine().split(" ")).iterator();
				return it.next();
			}catch(IOException e){
				throw new IllegalStateException();
			}
		}
		int nextInt() throws RuntimeException{
			return Integer.parseInt(next());
		}
		long nextLong() throws RuntimeException{
			return Long.parseLong(next());
		}
		double nextDouble() throws RuntimeException{
			return Double.parseDouble(next());
		}
		void close(){
			try{
				br.close();
			}catch(IOException e){
				throw new IllegalStateException();
			}
		}
	}
	private static class Printer extends PrintWriter{
		Printer(PrintStream out){
			super(out);
		}
	}


}
0