Advertisement
Guest User

Untitled

a guest
Feb 24th, 2017
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(int, char**)
  5. {
  6. int n,m;
  7. cin >> n >> m;
  8. vector<vector<int>> matrix(n, vector<int>(m,0));
  9. for(int i = 0; i < n; ++i) {
  10. for (int j = 0; j < m; ++j) {
  11. cin >> matrix[i][j];
  12. }
  13. }
  14.  
  15. vector<int> left2right(100001,0); // for every left border says the farest right one
  16. for (int j = 0; j < m; ++j) {
  17. int i = 1;
  18. int l = 0, start = 0;
  19. while (i <= n) {
  20. if (i < n && matrix[i-1][j] <= matrix[i][j]) {
  21. ++l;
  22. } else {
  23. if (l != 0) {
  24. for (int s = start; s <= start + l; ++s) {
  25. left2right[s] = max(left2right[s], start+l);
  26. }
  27. }
  28. start = i;
  29. l = 0;
  30. }
  31. ++i;
  32. }
  33. }
  34.  
  35. int k = 0;
  36. cin >> k;
  37. while(k > 0) {
  38. int l, r;
  39. cin >> l >> r;
  40. if (l == r) {
  41. cout << "Yes\n";
  42. --k;
  43. continue;
  44. }
  45. --l; --r;
  46. bool res = left2right[l] >= r;
  47. if (res)
  48. cout << "Yes\n";
  49. else
  50. cout << "No\n";
  51.  
  52. --k;
  53. }
  54. return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement