Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include "cstring"
- #include <algorithm>
- using namespace std;
- int high(pair <int, int> a, pair <int, int> b)
- {
- if (abs(b.second - a.second) > abs(b.first - a.first)) return -1;
- int l = -1, r = 100000000;
- while (l < r - 1)
- {
- int m = (l + r) / 2;
- pair <int, int> keep = make_pair(a.first + m, a.second + m);
- if (abs(b.second - keep.second) > abs(b.first - keep.first))
- r = m;
- else
- l = m;
- }
- return l;
- }
- int main()
- {
- int n, m;
- cin >> n >> m;
- pair <int, int> last;
- int result = -1;
- for (int i = 0; i < m; i++)
- {
- pair <int, int> cur;
- cin >> cur.first >> cur.second;
- result = max(result, cur.second);
- if (i == m - 1)
- result = max(result, cur.second + n - cur.first);
- if (i != 0)
- {
- int q = high(last, cur);
- if (q == -1)
- {
- cout << "IMPOSSIBLE";
- return 0;
- }
- result = max(last.second + q, result);
- }
- else
- result = max(result, cur.second + cur.first - 1);
- last = cur;
- }
- cout << result;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement