Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <queue>
- #include <tuple>
- #include <cmath>
- #include <algorithm>
- #include <vector>
- #define int long long
- using namespace std;
- bool sortbysecond(tuple<int, int, int>& a, tuple<int, int, int>& b) {
- return get<1>(a) < get<1>(b);
- }
- int binSearch(int start, int end, int number, vector<tuple<int, int, int>>& vect) {
- while (start != end) {
- int mid = (start + end + 1) / 2;
- if ((get<1>(vect[mid])) <= number) {
- start = mid;
- }
- else {
- end = mid - 1;
- }
- }
- return start;
- }
- main() {
- ifstream in("convention2.in");
- ofstream out("convention2.out");
- int N;
- in >> N;
- vector <tuple<int, int, int>> vals = {};
- priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> pq = {};
- for (int i = 1; i <= N; i++) {
- int b, c;
- in >> b >> c;
- vals.push_back(make_tuple(i, b, c));
- }
- sort(vals.begin(), vals.end(), sortbysecond);
- int pointer = 1;
- int prevfinishing = get<1>(vals[0]) + get<2>(vals[0]);
- int highestIndex = binSearch(pointer, N - 1, prevfinishing, vals);
- for (int i = pointer; i <= highestIndex; i++) {
- pq.push(vals[i]);
- }
- int maxwait = 0;
- int wait = 0;
- int arrivaltime = get<1>(vals[0]);
- pointer = highestIndex + 1;
- while (pointer < N) {
- int wait = prevfinishing - get<1>(pq.top());
- prevfinishing = max(prevfinishing + get<2>(pq.top()), get<1>(pq.top()) + get<2>(pq.top()));
- maxwait = max(wait, maxwait);
- pq.pop();
- highestIndex = binSearch(pointer, N - 1, prevfinishing, vals);
- for (int i = pointer; i <= highestIndex; i++) {
- pq.push(vals[i]);
- }
- pointer = highestIndex + 1;
- }
- while (!pq.empty()) {
- int wait = prevfinishing - get<1>(pq.top());
- prevfinishing = prevfinishing + get<2>(pq.top());
- maxwait = max(wait, maxwait);
- pq.pop();
- }
- out << maxwait;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement