Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- const int MOD = 1e9 + 7;
- int r, c, k;
- const int MAXN = 750;
- const int MAXK = MAXN * MAXN + 10;
- int dp[MAXN][MAXN];
- int summ[MAXN][MAXN];
- vector<int> t[MAXK];
- vector<pair<int, int>> a[MAXK];
- int sum(int color, int r) {
- int result = 0;
- for (; r >= 0; r = (r & (r + 1)) - 1)
- result += t[color][r];
- return result;
- }
- void inc(int i, int delta, int color) {
- for (; i < (int) a[color].size(); i = (i | (i + 1)))
- t[color][i] += delta;
- }
- int bin(int color, int j) {
- int left = 0, right = a[color].size() + 1, mid;
- while (left != right - 1) {
- mid = (left + right) / 2;
- if (a[color][mid].first > j) {
- right = mid;
- } else {
- left = mid;
- }
- }
- return left;
- }
- int main() {
- // freopen("hopscotch.in", "r", stdin), freopen("hopscotch.out", "w", stdout);
- ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- cin >> r >> c >> k;
- int matr[r][c];
- set<int> s[k + 1];
- for (int i = 0; i < r; ++i) {
- for (int j = 0; j < c; ++j) {
- cin >> matr[i][j];
- s[matr[i][j]].insert(j);
- }
- }
- for (int i = 1; i <= k; ++i) {
- t[i].resize(s[i].size());
- t[i].assign(s[i].size(), 0);
- for (auto l : s[i]) {
- a[i].push_back( { l, 0 });
- }
- }
- summ[0][0] = 1;
- for (int i = 1; i < r; ++i)
- summ[i][0] = 1;
- for (int i = 1; i < c; ++i)
- summ[0][i] = 1;
- inc(0, 1, matr[0][0]);
- for (int i = 1; i < r; ++i) {
- for (int j = 1; j < c; ++j) {
- int subsum = summ[i - 1][j - 1];
- int color = matr[i][j];
- int left = bin(color, j);
- int cur = bin(color, j - 1);
- int minus = sum(color, cur);
- // if (i == 1 && j == 3) { cout << minus << endl;}
- if (a[color][cur].first >= j) {
- minus -= a[color][cur].second;
- }
- /*
- if (i == 1 && j == 3) {
- cout << "cur = " << cur << endl;
- cout << a[color][cur].first << " " << a[color][cur].second
- << endl;
- cout << color << " " << subsum << " " << minus << endl;
- return 0;
- }*/
- int ans = subsum - minus;
- summ[i][j] = subsum + ans;
- a[color][left].second += ans;
- inc(left, ans, color);
- // return 0;
- }
- }
- for (int i = 0; i < r; ++i) {
- for (int j = 0; j < c; ++j) {
- cout << summ[i][j] << " ";
- }
- cout << endl;
- }
- // cout << summ[r - 1][c - 1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement