結果

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

ソースコード

diff # 

package yukicoder;
import java.util.Arrays;
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;
	}


}
0