Advertisement
Guest User

Untitled

a guest
Apr 26th, 2015
190
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.27 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include "cstring"
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8.  
  9. int high(pair <int, int> a, pair <int, int> b)
  10. {
  11. if (abs(b.second - a.second) > abs(b.first - a.first)) return -1;
  12. int l = -1, r = 100000000;
  13. while (l < r - 1)
  14. {
  15. int m = (l + r) / 2;
  16. pair <int, int> keep = make_pair(a.first + m, a.second + m);
  17. if (abs(b.second - keep.second) > abs(b.first - keep.first))
  18. r = m;
  19. else
  20. l = m;
  21. }
  22. return l;
  23. }
  24.  
  25. int main()
  26. {
  27. int n, m;
  28. cin >> n >> m;
  29. pair <int, int> last;
  30. int result = -1;
  31. for (int i = 0; i < m; i++)
  32. {
  33. pair <int, int> cur;
  34. cin >> cur.first >> cur.second;
  35. result = max(result, cur.second);
  36. if (i == m - 1)
  37. result = max(result, cur.second + n - cur.first);
  38. if (i != 0)
  39. {
  40. int q = high(last, cur);
  41. if (q == -1)
  42. {
  43. cout << "IMPOSSIBLE";
  44. return 0;
  45. }
  46. result = max(last.second + q, result);
  47. }
  48. else
  49. result = max(result, cur.second + cur.first - 1);
  50. last = cur;
  51. }
  52. cout << result;
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement