Advertisement
Guest User

Untitled

a guest
Nov 20th, 2017
51
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.28 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. int r, c, k;
  9.  
  10. const int MAXN = 750;
  11. const int MAXK = MAXN * MAXN + 10;
  12.  
  13. int dp[MAXN][MAXN];
  14. int summ[MAXN][MAXN];
  15. vector<int> t[MAXK];
  16. vector<pair<int, int>> a[MAXK];
  17.  
  18. int sum(int color, int r) {
  19. int result = 0;
  20. for (; r >= 0; r = (r & (r + 1)) - 1)
  21. result += t[color][r];
  22. return result;
  23. }
  24.  
  25. void inc(int i, int delta, int color) {
  26. for (; i < (int) a[color].size(); i = (i | (i + 1)))
  27. t[color][i] += delta;
  28. }
  29.  
  30. int bin(int color, int j) {
  31. int left = 0, right = a[color].size() + 1, mid;
  32. while (left != right - 1) {
  33. mid = (left + right) / 2;
  34. if (a[color][mid].first > j) {
  35. right = mid;
  36. } else {
  37. left = mid;
  38. }
  39. }
  40. return left;
  41. }
  42.  
  43. int main() {
  44. // freopen("hopscotch.in", "r", stdin), freopen("hopscotch.out", "w", stdout);
  45. ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  46. cin >> r >> c >> k;
  47. int matr[r][c];
  48. set<int> s[k + 1];
  49. for (int i = 0; i < r; ++i) {
  50. for (int j = 0; j < c; ++j) {
  51. cin >> matr[i][j];
  52. s[matr[i][j]].insert(j);
  53. }
  54. }
  55. for (int i = 1; i <= k; ++i) {
  56. t[i].resize(s[i].size());
  57. t[i].assign(s[i].size(), 0);
  58. for (auto l : s[i]) {
  59. a[i].push_back( { l, 0 });
  60. }
  61. }
  62. summ[0][0] = 1;
  63. for (int i = 1; i < r; ++i)
  64. summ[i][0] = 1;
  65. for (int i = 1; i < c; ++i)
  66. summ[0][i] = 1;
  67. inc(0, 1, matr[0][0]);
  68. for (int i = 1; i < r; ++i) {
  69. for (int j = 1; j < c; ++j) {
  70. int subsum = summ[i - 1][j - 1];
  71. int color = matr[i][j];
  72. int left = bin(color, j);
  73. int cur = bin(color, j - 1);
  74. int minus = sum(color, cur);
  75. // if (i == 1 && j == 3) { cout << minus << endl;}
  76. if (a[color][cur].first >= j) {
  77. minus -= a[color][cur].second;
  78. }
  79. /*
  80. if (i == 1 && j == 3) {
  81. cout << "cur = " << cur << endl;
  82. cout << a[color][cur].first << " " << a[color][cur].second
  83. << endl;
  84. cout << color << " " << subsum << " " << minus << endl;
  85. return 0;
  86. }*/
  87. int ans = subsum - minus;
  88. summ[i][j] = subsum + ans;
  89. a[color][left].second += ans;
  90. inc(left, ans, color);
  91. // return 0;
  92. }
  93. }
  94. for (int i = 0; i < r; ++i) {
  95. for (int j = 0; j < c; ++j) {
  96. cout << summ[i][j] << " ";
  97. }
  98. cout << endl;
  99. }
  100. // cout << summ[r - 1][c - 1];
  101. return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement