Guest User

Untitled

a guest
Dec 3rd, 2014
155
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