Submission #951906

---

Source Code Expand

#include <vector>
#include <iostream>
#include <set>
#include <cstdio>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <cmath>
#include <complex>
#include <algorithm>
#include <tuple>
#include <algorithm>
#include <limits>
#include <map>
#include <valarray>
#include <list>
 
using namespace std;
 
typedef long long ll;
 
template<class T>
struct Pi {
    T x, y;
    Pi() {}
    Pi(T xx, T yy) {
        x = xx; y = yy;
    }
    bool operator<(const Pi &r) const {
        if (x != r.x) return x < r.x;
        return y < r.y;
    }
    bool operator>(const Pi &r) const {
        if (x != r.x) return x > r.x;
        return y > r.y;
    }
    bool operator==(const Pi &r) const {
        if (x != r.x) return false;
        return y == r.y;
    }
};
 
template<class T>
struct Ti {
    T x, y, z;
    Ti() {}
    Ti(T xx, T yy, T zz) {
        x = xx; y = yy; z = zz;
    }
    bool operator<(const Ti &r) const {
        if (x != r.x) return x < r.x;
        if (y != r.y) return y < r.y;
        return z < r.z;
    }
    bool operator>(const Ti &r) const {
        if (x != r.x) return x > r.x;
        if (y != r.y) return y > r.y;
        return z > r.z;
    }
    bool operator==(const Ti &r) const {
        if (x != r.x) return false;
        if (y != r.y) return false;
        return z == r.z;
    }
};
 
const int MN = 520;
const int MK = 110;
int g[MN][MN];
int sum[MK][MN][MN] = {};
int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> g[i][j]; g[i][j]--;
        }
    }
    for (int kk = 0; kk < k; kk++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                sum[kk][i][j] = sum[kk][i][j-1] + sum[kk][i-1][j]
                + (g[i-1][j-1] == kk) - sum[kk][i-1][j-1];
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int t, a1, b1, a2, b2;
        cin >> t >> a1 >> b1 >> a2 >> b2;
        a1--; b1--;
        if (t == 1) {
            a2--; b2--;
            if (a1 > a2 || b1 > b2) {
                swap(a1, a2);
                swap(b1, b2);
            } 
            int k1 = g[a1][b1], k2 = g[a2][b2];
            swap(g[a1][b1], g[a2][b2]);
            int i, j;
            i = a1+1;
            for (int j = b1+1; j <= m; j++) {
                sum[k1][i][j] = sum[k1][i][j-1] + sum[k1][i-1][j]
                + (g[i-1][j-1] == k1) - sum[k1][i-1][j-1];
                sum[k2][i][j] = sum[k2][i][j-1] + sum[k2][i-1][j]
                + (g[i-1][j-1] == k2) - sum[k2][i-1][j-1];
            }
            j = b1 + 1;
            for (int i = a1+1; i <= n; i++) {
                sum[k1][i][j] = sum[k1][i][j-1] + sum[k1][i-1][j]
                + (g[i-1][j-1] == k1) - sum[k1][i-1][j-1];
                sum[k2][i][j] = sum[k2][i][j-1] + sum[k2][i-1][j]
                + (g[i-1][j-1] == k2) - sum[k2][i-1][j-1];
            }
        } else {
            int kk[100] = {};
            for (int i = 0; i < k; i++) {
                kk[i] = sum[i][a2][b2] - sum[i][a1][b2]
                - sum[i][a2][b1] + sum[i][a1][b1];
            }
            int ma = 0, mk = 0;
            for (int i = 0; i < k; i++) {
                if (ma <= kk[i]) {
                    ma = kk[i];
                    mk = i;
                }
            }
            printf("%d %d\n", mk+1, ma);
        }
    }
    return 0;
}

Submission Info

Judge Result