Advertisement
Guest User

Untitled

a guest
Oct 17th, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define EPS 1e-6
  6. #define mod 1000000007
  7.  
  8.  
  9. int first_in_range(const vector<int> &vec, int l, int r) {
  10. for (int i = 0; i < vec.size(); ++i) {
  11. if (vec[i] > l && vec[i] <= r) {
  12. return vec[i];
  13. }
  14. }
  15. return r;
  16. }
  17.  
  18. int last_in_range(const vector<int> &vec, int l, int r) {
  19. for (int i = (int)(vec.size()) - 1; i >= 0; --i) {
  20.  
  21. if (vec[i] >= l && vec[i] < r) {
  22. return vec[i];
  23. }
  24. }
  25. return l;
  26. }
  27.  
  28.  
  29. signed main() {
  30. int n, m, k;
  31. cin >> n >> m >> k;
  32. vector<vector<int>> vert(m + 1);
  33. vector<vector<int>> hori(n + 1);
  34. for (int i = 0; i < k; ++i) {
  35. int x, y;
  36. cin >> x >> y;
  37. hori[x].push_back(y);
  38. vert[y].push_back(x);
  39. }
  40. for (int j = 0; j < m + 1; ++j) {
  41. sort(vert[j].begin(), vert[j].end());
  42. }
  43. for (int j = 0; j < n + 1; ++j) {
  44. sort(hori[j].begin(), hori[j].end());
  45. }
  46. int x = 1, y = 0, d = 1;
  47. int up = 0;
  48. int left = 0;
  49. int down = n + 1;
  50. int right = m + 1;
  51. int cnt = 0;
  52.  
  53.  
  54. int lx = -1;
  55. int ly = -1;
  56.  
  57. int l1x = -2;
  58. int l1y = -2;
  59. while (true) {
  60. l1x = lx;
  61. l1y = ly;
  62. lx = x;
  63. ly = y;
  64. if (l1x == lx && lx == x &&
  65. l1y == ly && ly == y) {
  66. break;
  67. }
  68. if (d == 1) {
  69. int y1 = first_in_range(hori[x], y, right);
  70. left = y;
  71. cnt += y1 - y - 1;
  72. y = y1 - 1;
  73. } else if (d == 2) {
  74. int x1 = first_in_range(vert[y], x, down);
  75. up = x;
  76. cnt += x1 - x - 1;
  77. x = x1 - 1;
  78. } else if (d == 3) {
  79. int y1 = last_in_range(hori[x], left, y);
  80. right = y;
  81. cnt += y - y1 - 1;
  82. y = y1 + 1;
  83. } else {
  84. int x1 = last_in_range(vert[y], up, x);
  85. down = x;
  86. cnt += x - x1 - 1;
  87. x = x1 + 1;
  88. }
  89.  
  90. d = (d) % 4 + 1;
  91. }
  92. cout << (cnt + k == n * m ? "Yes" : "No");
  93.  
  94. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement