Advertisement
a_chn

Untitled

Jan 18th, 2024
843
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <queue>
  4. #include <tuple>
  5. #include <cmath>
  6. #include <algorithm>
  7. #include <vector>
  8. #define int long long
  9.  
  10. using namespace std;
  11.  
  12.  
  13. bool sortbysecond(tuple<int, int, int>& a, tuple<int, int, int>& b) {
  14.     return get<1>(a) < get<1>(b);
  15. }
  16.  
  17. int binSearch(int start, int end, int number, vector<tuple<int, int, int>>& vect) {
  18.  
  19.     while (start != end) {
  20.         int mid = (start + end + 1) / 2;
  21.  
  22.         if ((get<1>(vect[mid])) <= number) {
  23.             start = mid;
  24.         }
  25.         else {
  26.             end = mid - 1;
  27.         }
  28.     }
  29.  
  30.     return start;
  31.  
  32. }
  33.  
  34.  
  35. main() {
  36.  
  37.     ifstream in("convention2.in");
  38.     ofstream out("convention2.out");
  39.  
  40.  
  41.     int N;
  42.     in >> N;
  43.  
  44.     vector <tuple<int, int, int>> vals = {};
  45.     priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq = {};
  46.  
  47.  
  48.     for (int i = 1; i <= N; i++) {
  49.         int b, c;
  50.         in >> b >> c;
  51.         vals.push_back(make_tuple(i, b, c));
  52.     }
  53.  
  54.     sort(vals.begin(), vals.end(), sortbysecond);
  55.  
  56.     int pointer = 1;
  57.     int prevfinishing = get<1>(vals[0]) + get<2>(vals[0]);
  58.     int highestIndex = binSearch(pointer, N - 1, prevfinishing, vals);
  59.  
  60.     for (int i = pointer; i <= highestIndex; i++) {
  61.         pq.push(vals[i]);
  62.     }
  63.  
  64.     int maxwait = 0;
  65.     int wait = 0;
  66.     int arrivaltime = get<1>(vals[0]);
  67.     pointer = highestIndex + 1;
  68.     while (pointer < N) {
  69.  
  70.         int wait = prevfinishing - get<1>(pq.top());
  71.         prevfinishing = max(prevfinishing + get<2>(pq.top()), get<1>(pq.top()) + get<2>(pq.top()));
  72.         maxwait = max(wait, maxwait);
  73.         pq.pop();
  74.         highestIndex = binSearch(pointer, N - 1, prevfinishing, vals);
  75.         for (int i = pointer; i <= highestIndex; i++) {
  76.             pq.push(vals[i]);
  77.         }
  78.  
  79.         pointer = highestIndex + 1;
  80.     }
  81.  
  82.     while (!pq.empty()) {
  83.         int wait = prevfinishing - get<1>(pq.top());
  84.         prevfinishing = prevfinishing + get<2>(pq.top());
  85.         maxwait = max(wait, maxwait);
  86.         pq.pop();
  87.     }
  88.  
  89.     out << maxwait;
  90.  
  91.  
  92.  
  93.  
  94.  
  95.  
  96.  
  97.     return 0;
  98. }
  99.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement