結果

問題 No.3016 unordered_mapなるたけ落とすマン
ユーザー 37zigen37zigen
提出日時 2016-05-22 01:14:12
言語 Java21
(openjdk 21)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 143 ms
42,432 KB
testcase_01 AC 145 ms
42,324 KB
testcase_02 AC 153 ms
42,176 KB
testcase_03 TLE -
testcase_04 TLE -
testcase_05 TLE -
testcase_06 TLE -
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
testcase_14 TLE -
testcase_15 TLE -
testcase_16 TLE -
testcase_17 TLE -
testcase_18 TLE -
testcase_19 TLE -
testcase_20 TLE -
testcase_21 TLE -
testcase_22 TLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 TLE -
testcase_27 TLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 TLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 AC 137 ms
42,212 KB
testcase_42 AC 135 ms
41,888 KB
testcase_43 AC 148 ms
42,132 KB
testcase_44 MLE -
testcase_45 AC 449 ms
47,376 KB
testcase_46 MLE -
testcase_47 TLE -
testcase_48 TLE -
testcase_49 TLE -
testcase_50 MLE -
権限があれば一括ダウンロードができます

ソースコード

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