Advertisement
Guest User

Untitled

a guest
Feb 24th, 2017
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.36 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. typedef vector<int> VI;
  6. typedef vector<VI> VVI;
  7.  
  8. #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
  9. #define REP(i, n) FOR(i, 0, n)
  10. #define INF (1LL<<25) //33554432
  11.  
  12. int d[100010];
  13. signed main(void)
  14. {
  15. //入力
  16. int n, m;
  17. scanf("%d%d", &n, &m);
  18. VVI a(n, (VI(m, 0)));
  19. REP(i, n) REP(j, m) scanf("%d", &a[i][j]);
  20.  
  21. //降順でない列が開始する行
  22. int s = -1;
  23. //降順でない部分列が何行から何行に存在するのかを求める
  24. REP(i, m) {
  25. s = -1;
  26. FOR(j, 1, n) {
  27. if(a[j][i] >= a[j-1][i]) {
  28. if(s == -1) s = j-1;
  29. d[s] = max(d[s], (int)j);
  30. } else {
  31. s = -1;
  32. }
  33. }
  34. }
  35. //例として0行から3行が降順でない列のときd[0] = 3となっている
  36. //d[1] = d[2] = d[3] = 3 と間を埋める
  37. int ret = -INF;
  38. REP(i, n) {
  39. ret = max(ret, d[i]);
  40. if(ret < i) ret = i;
  41. d[i] = ret;
  42. }
  43.  
  44. //クエリに答える
  45. int k;
  46. scanf("%d", &k);
  47. REP(i, k) {
  48. int l, r;
  49. scanf("%d%d", &l, &r);
  50. l--; r--;
  51. if(l == r) {
  52. //数1個からなる数列は降順でない列
  53. cout << "Yes" << endl;
  54. } else if(d[l] >= r) {
  55. //rが最大の降順でない行以下ならば降順でない列が存在する
  56. cout << "Yes" << endl;
  57. } else {
  58. cout << "No" << endl;
  59. }
  60. }
  61.  
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement