rakcode1998

Untitled

Jan 18th, 2017
286
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 4.63 KB | None | 0 0
  1. package a2oj;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.FileNotFoundException;
  5. import java.io.FileReader;
  6. import java.io.IOException;
  7. import java.io.InputStream;
  8. import java.io.InputStreamReader;
  9. import java.io.OutputStream;
  10. import java.io.PrintWriter;
  11. import java.util.Arrays;
  12. import java.util.Map;
  13. import java.util.SortedSet;
  14. import java.util.StringTokenizer;
  15. import java.util.TreeMap;
  16. import java.util.TreeSet;
  17.  
  18. /**
  19.  * Created by Rakshit on 17/1/17.
  20.  * Java is Love and Code is Beautiful..
  21.  */
  22. public class Query{
  23.     static class InputReader
  24.     {
  25.         public BufferedReader reader;
  26.         public StringTokenizer tok;
  27.  
  28.         public InputReader(InputStream inputStream)
  29.         {
  30.             reader =new BufferedReader(new InputStreamReader(inputStream));
  31.             tok=null;
  32.         }
  33.  
  34.         public InputReader(String inputFile) throws FileNotFoundException
  35.         {
  36.             reader=new BufferedReader(new FileReader(inputFile));
  37.             tok=null;
  38.         }
  39.  
  40.         public String nextLine()
  41.         {
  42.             String c="";
  43.             try
  44.             {
  45.                 c+=reader.readLine();
  46.             }
  47.             catch(IOException e)
  48.             {
  49.                 throw new RuntimeException(e);
  50.             }
  51.  
  52.             return c;
  53.         }
  54.  
  55.         public String next()
  56.         {
  57.             while(tok==null || !tok.hasMoreTokens())
  58.             {
  59.                 try
  60.                 {
  61.                     tok=new StringTokenizer(nextLine());
  62.                 }
  63.                 catch(Exception e)
  64.                 {
  65.                     throw new RuntimeException(e);
  66.                 }
  67.             }
  68.  
  69.             return tok.nextToken();
  70.         }
  71.  
  72.         public int nextInt()
  73.         {
  74.             return Integer.parseInt(next());
  75.         }
  76.  
  77.         public long nextLong()
  78.         {
  79.             return Long.parseLong(next());
  80.         }
  81.  
  82.         public double nextDouble()
  83.         {
  84.             return Double.parseDouble(next());
  85.         }
  86.     }
  87.  
  88.     public static void main(String args[])
  89.     {
  90.         InputStream inputstream=System.in;
  91.         OutputStream outputstream=System.out;
  92.         InputReader in=new InputReader(inputstream);
  93.         PrintWriter out=new PrintWriter (outputstream);
  94.         Task solver=new Task();
  95.         solver.solve(in,out);
  96.     }
  97.  
  98.     static class Task
  99.     {
  100.         public final int INF =100000000;
  101.         public void solve(InputReader in , PrintWriter out)
  102.         {
  103.             int n=in.nextInt();
  104.             int m=in.nextInt();
  105.             SortedSet<Integer> check=new TreeSet();
  106.  
  107.             int a[]=new int [n];
  108.             int b[]=new int [m];
  109.  
  110.             for(int i=0 ;i<n ;i++)
  111.             {
  112.                 a[i]=in.nextInt();
  113.             }
  114.  
  115.             for(int i=0 ;i<m ;i++)
  116.             {
  117.                 b[i]=in.nextInt();
  118.                 check.add(b[i]);
  119.             }
  120.  
  121.             Arrays.sort(a);
  122.             int res[]=new int [m];
  123.             int l=check.size();
  124.             Map<Integer,Integer> store=new TreeMap();
  125.             Map<Integer,Integer> good=new TreeMap();
  126.  
  127.             for(int i=0 ;i<n ;i++)
  128.             {
  129.                 good.put(a[i],i);
  130.          //       for(Map.Entry<Integer,Integer>entry:good.entrySet())
  131.         //        {
  132.        //             out.println(entry.getKey()+" "+entry.getValue());
  133.        //         }
  134.             }
  135.  
  136.         //    for(Map.Entry<Integer,Integer>entry:good.entrySet())
  137.        //     {
  138.        //         out.println(entry.getKey()+" "+entry.getValue());
  139.        //     }
  140.  
  141.             int s;
  142.  
  143.             Integer[] c=check.toArray(new Integer[check.size()]);
  144.  
  145.             for(int i=0 ;i<l ;i++)
  146.             {
  147.                 if(good.containsKey(c[i]))
  148.                 {
  149.                     store.put(c[i],good.get(c[i])+1);
  150.                 }
  151.                 else
  152.                 {
  153.                     s=Arrays.binarySearch(a,c[i]);
  154.                     s=-(s+1);
  155.                     store.put(c[i],s);
  156.                 }
  157.             }
  158.  
  159.             for(int i=0 ;i<m ;i++)
  160.             {
  161.                 res[i]=store.get(b[i]);
  162.             }
  163.  
  164.             for(int i=0 ;i<m ;i++)
  165.             {
  166.                 out.print(res[i]+" ");
  167.             }
  168.             out.flush();
  169.         }
  170.  
  171.         public long fac(int n)
  172.         {
  173.             long f[]=new long [n+1];
  174.             f[0]=1;
  175.  
  176.             for(int i=1 ;i<n+1 ;i++)
  177.             {
  178.                 f[i]=i*f[i-1];
  179.             }
  180.  
  181.             return f[n];
  182.         }
  183.  
  184.         public long c(int n,int a,int b)
  185.         {
  186.             return fac(n)/(fac(a)*fac(b));
  187.         }
  188.     }
  189. }
Add Comment
Please, Sign In to add comment