SHARE
TWEET

Untitled

a guest Oct 1st, 2018 24 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //package CodeChef;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.BufferedWriter;
  5. import java.io.InputStreamReader;
  6. import java.io.OutputStreamWriter;
  7.  
  8. import java.util.ArrayList;
  9. import java.util.Arrays;
  10. import java.util.Comparator;
  11.  
  12.  
  13.  
  14.  
  15. /*public*/ class CHEFRES_FAST {
  16.     public CHEFRES_FAST() {
  17.         super();
  18.     }
  19.    
  20.     public static long modifiedBS(Period[] periods, long t) {
  21.         if( t >= periods[periods.length-1].end) {
  22.             return -1L;
  23.         }
  24.         else if(t <= periods[0].start){
  25.             return (periods[0].start - t);
  26.         }
  27.         else {
  28.             int lo = 0;
  29.             int hi = periods.length - 1;
  30.             int mid;
  31.             while(lo < hi) {
  32.                 mid = ((hi-lo+1)/2);
  33.                
  34.                 if( t >= periods[mid].start ) {
  35.                     lo = mid;
  36.                 }
  37.                 else {
  38.                     hi = mid-1;
  39.                 }
  40.             }
  41.            
  42.             if( (t >= periods[lo].start) && ( t < periods[lo].end ) ) {
  43.                 return 0L;
  44.             }
  45.             else {
  46.                 return ( periods[lo+1].start - t );
  47.             }
  48.         }
  49.     }
  50.    
  51.     public static void main(String[] args)throws Exception {
  52.         BufferedReader in = new BufferedReader (new InputStreamReader(System.in));
  53.         BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
  54.        
  55.         String[] s = in.readLine().split(" ");
  56.        
  57.         int t = Integer.parseInt(s[0]);
  58.        
  59.         //ArrayList<Long> ans = new ArrayList<>();
  60.        
  61.         while(t-- > 0) {
  62.             s = in.readLine().split(" ");
  63.             int n = Integer.parseInt(s[0]);
  64.             int m = Integer.parseInt(s[1]);
  65.             Period[] periods = new Period[n];
  66.             long[] ans = new long[m];
  67.            
  68.             for(int i=0; i<n; i++) {
  69.                 s = in.readLine().split(" ");
  70.                 periods[i] = new Period(Long.parseLong(s[0]),Long.parseLong(s[1]));    
  71.             }
  72.            
  73.             Arrival[] times = new Arrival[m];
  74.            
  75.             for(int i=0; i<m; i++) {
  76.                 s = in.readLine().split(" ");
  77.                 times[i] = new Arrival(Long.parseLong(s[0]),i);
  78.             }
  79.            
  80.             Arrays.sort( periods, new MyComparator() );
  81.             Arrays.sort( times, new MyComparator1() );
  82.            
  83.             int p1 = 0;
  84.             int p2 = 0;
  85.            
  86.             while(times[p2].time < periods[0].start) {
  87.                 ans[times[p2].customerNumber] = (periods[0].start - times[p2].time);
  88.                 p2++;
  89.             }
  90.            
  91.             while( (p1 < n) && (p2 < m) ) {
  92.                
  93.                 if( (times[p2].time >= periods[p1].start)  ) {
  94.                     if( times[p2].time < periods[p1].end ) {
  95.                         ans[times[p2].customerNumber] = 0;
  96.                         p2++;
  97.                     }
  98.                     else /*if( times[p2].time > periods[p1].end )*/ {
  99.                         if( p1 < (n-1) ) {
  100.                             if( times[p2].time >= periods[p1+1].start ) {
  101.                                 p1++;
  102.                             }
  103.                             else {
  104.                                 ans[times[p2].customerNumber] = periods[p1+1].start - times[p2].time;
  105.                                 p2++;
  106.                             }
  107.                         }
  108.                         else {
  109.                             ans[times[p2].customerNumber] = -1;
  110.                             p2++;
  111.                         }
  112.                     }
  113.                 }
  114.             }
  115.            
  116.             for(int i=0; i<ans.length; i++) {
  117.                 log.write(Long.toString(ans[i])+"\n");
  118.             }
  119.  
  120.         }    
  121.        
  122.         log.flush();
  123.         in.close();
  124.     }
  125. }
  126.  
  127. class Period {
  128.     long start;
  129.     long end;
  130.    
  131.     Period(long s, long e) {
  132.         start = s;
  133.         end = e;
  134.     }
  135. }
  136.  
  137. class Arrival {
  138.     long time;
  139.     int customerNumber;
  140.    
  141.     Arrival(long t, int cNum) {
  142.         time = t;
  143.         customerNumber = cNum;
  144.     }
  145. }
  146.  
  147. class MyComparator1 implements Comparator<Arrival> {
  148.     public int compare(Arrival a1, Arrival a2) {
  149.         if(a1.time < a2.time) {
  150.             return -1;
  151.         }
  152.         else {
  153.             return 1;
  154.         }
  155.     }
  156. }
  157.  
  158. class MyComparator implements Comparator<Period>{
  159.  
  160.     public int compare(Period p1, Period p2) {
  161.         if(p1.start < p2.start) {
  162.             return -1;
  163.         }
  164.         else {
  165.             return 1;
  166.         }
  167.     }
  168. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top