SHARE
TWEET

Untitled

a guest Dec 3rd, 2014 148 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int t = 1000001;
  8. int V, W;
  9.  
  10. struct contest{
  11.  int start;
  12.  int end;
  13. };
  14.  
  15. bool contestcomp(contest a, contest b) {
  16.   return ((a.start < b.start) ? 1:0);
  17. };
  18.  
  19. int beststartingtime(int X[], int start, int ll, int ul){
  20.  
  21.  if(start < X[0])
  22.  return -1;
  23.  
  24.  if(X[ul] < start)
  25.  return X[ul];
  26.  
  27.  //Starting point exists
  28.  
  29.  while(ul > ll)
  30.  {
  31.    // cout << X[ll] << " " << X[(ul+ll)/2 + 1] << " " << X[ul] << endl;
  32.     if(X[(ul+ll)/2] == start)
  33.         return start;
  34.         else if(X[(ul+ll)/2] < start)
  35.         {
  36.         if(X[(ul+ll)/2 + 1] > start)
  37.         return X[(ul+ll)/2];
  38.         else
  39.         return beststartingtime(X, start, (ul+ll)/2, ul);
  40.         }
  41.         else
  42.         {
  43.         return beststartingtime(X, start, ll, (ul+ll)/2);
  44.         }
  45.  
  46.  }
  47.  return -1;
  48. }
  49.  
  50.  
  51. int main()
  52. {
  53.  ios::sync_with_stdio(false);
  54.  int N; //N = contests, V = V wormholes, W = W wormholes
  55.  cin >> N >> V >> W;
  56.  contest contests[N];
  57.  
  58.  for(int i = 0; i < N; i++)
  59.  cin >> contests[i].start >> contests[i].end;
  60.  
  61.  sort(contests, contests + N, contestcomp);
  62.  
  63.  int X[V]; //Wormhole V starting times;
  64.  int Y[W]; //Wormhole W ending times;
  65.  
  66.  for(int i = 0; i < V; i++)
  67.  cin >> X[i];
  68.  
  69.  sort(X, X + V);
  70.  
  71.  for(int i = 0; i < W; i++)
  72.  cin >> Y[i];
  73.  
  74.  sort(Y, Y + W);
  75.  
  76.  //Scanning complete
  77.  
  78.  int k = 0;
  79.  for(int i = 0; i < N; i++) //iterate through contests;
  80.  {
  81.     int beststart = beststartingtime(X, contests[i].start, 0, V-1);
  82.         if(beststart == -1)
  83.         break;
  84.         //cout << beststart << endl;
  85.         int bestend = -1;
  86.         for(int j = 0; j < W; j++)
  87.         {
  88.         if(Y[j] >= contests[i].end){
  89.         bestend = Y[j];
  90.         break;
  91.         }
  92.         }
  93.         if(beststart != -1 & bestend != -1)
  94.         t = min(t, bestend - beststart + 1);
  95.  
  96.  }
  97.  cout << t;
  98.  
  99. }
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