結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 MLE -
testcase_02 MLE -
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 MLE -
testcase_23 TLE -
testcase_24 TLE -
testcase_25 TLE -
testcase_26 MLE -
testcase_27 MLE -
testcase_28 TLE -
testcase_29 TLE -
testcase_30 TLE -
testcase_31 TLE -
testcase_32 TLE -
testcase_33 MLE -
testcase_34 TLE -
testcase_35 TLE -
testcase_36 TLE -
testcase_37 TLE -
testcase_38 TLE -
testcase_39 TLE -
testcase_40 TLE -
testcase_41 MLE -
testcase_42 MLE -
testcase_43 MLE -
testcase_44 MLE -
testcase_45 MLE -
testcase_46 MLE -
testcase_47 MLE -
testcase_48 MLE -
testcase_49 MLE -
testcase_50 MLE -
権限があれば一括ダウンロードができます

ソースコード

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