Editorial for Bedao Regular Contest 05 - SQRSUM


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Code mẫu

#include <bits/stdc++.h>

using namespace std;

#define fo(i, a, b) for(int i = a; i <= b; i++)
#define _fo(i, a, b) for(int i = a; i >= b; i--)
#define foa(i, a) for (auto &i : a)
#define sz(a) ((int) a.size())
#define all(a) begin(a), end(a)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mk(x, y) make_pair(x, y)

typedef unsigned long long ull; 
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAX = 1e5+5;
const int LOG = 20;
const ll MOD = 1e9+7;
const ll INF = 1e15+5;
const int SQRT = 44721;

int n, m, q;
vector<vector<ll>> mat, pref;
vector<vector<vector<ll>>> ver, hor, corner_1, corner_2;
vector<pii> color[MAX];

ll rect(int x1, int y1, int x2, int y2) {
    return pref[x2][y2]-pref[x1-1][y2]-pref[x2][y1-1]+pref[x1-1][y1-1];
}

void precompute() {
    fo(i, 1, n) {
        fo(j, 1, m) {
            pref[i][j] = mat[i][j]+pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1];
        }
    }

    fo(i, 1, n) {
        fo(j, 1, m) {
            int temp = min(i, j);
            ver[i][j].assign(temp+1, 0); 
            if(temp > 1) ver[i][j][1] = rect(i-1, j-1, i, j);
            fo(k, 2, temp-1) ver[i][j][k] = rect(i-k, j-k, i, j)-rect(i-k+1, j-k+1, i-1, j-1)+ver[i][j][k-1]+ver[i-1][j-1][k-1]-ver[i-1][j-1][k-2]; 
        }
    }
    // corner_1
    fo(i, 1, n) {
        fo(j, 1, m) {
            int temp = min(i, j);
            corner_1[i][j].assign(temp, 0); 
            fo(k, 1, temp-1) corner_1[i][j][k] = ver[i][j][k]+corner_1[i][j-1][k-1]; 
        }
    }
    // corner_2 
    fo(i, 1, n) {
        fo(j, 1, m) {
            int temp = min(i, j);
            corner_2[i][j].assign(temp, 0); 
            fo(k, 1, temp-1) corner_2[i][j][k] = ver[i][j][k]+corner_2[i-1][j][k-1]; 
        }
    }
    //hor
    fo(i, 1, n) {
        fo(j, 1, m) {
            int temp = min(i, j);
            hor[i][j].assign(temp+1, 0); 
            fo(k, 1, temp-1) hor[i][j][k] = ver[i][j][k]+hor[i][j-1][k];  
        }
    }
    //ver
    fo(i, 1, n) {
        fo(j, 1, m) {
            int temp = min(i, j);
            fo(k, 1, temp-1) ver[i][j][k] = ver[i][j][k]+ver[i-1][j][k];   
        }
    }
}

ll get(int c1, int c2) { 
    ll res = 0;
    foa(p1, color[c1]) {
        foa(p2, color[c2]) {
            int x1 = min(p1.fi, p2.fi), y1 = min(p1.se, p2.se), x2 = max(p1.fi, p2.fi), y2 = max(p1.se, p2.se);  
            int dx = x2-x1, dy = y2-y1;        
            if(dx == 0 || dy == 0) continue;
            if(dx < dy) {
                x1 += dx;  
                y1 += dx;
                res ^= hor[x2][y2][dx]-hor[x1][y1-1][dx]+corner_1[x1][y1-1][dx-1]+corner_2[x2-1][y2][dx-1];                            
            }
            else {
                x1 += dy;  
                y1 += dy;                
                res ^= ver[x2][y2][dy]-ver[x1-1][y1][dy]+corner_2[x1-1][y1][dy-1]+corner_1[x2][y2-1][dy-1];
            }
        }
    }
    return res;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 
//    freopen("SQRSUM.INP", "r", stdin); 
//    freopen("SQRSUM.OUT", "w", stdout); 
    cin >> n >> m >> q;
    mat.assign(n+1, vector<ll>(m+1, 0));
    pref.assign(n+1, vector<ll>(m+1, 0));
    ver.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
    hor.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
    corner_1.assign(n+1, vector<vector<ll>>(m+1, vector<ll>()));
    corner_2.assign(n+1, vector<vector<ll>>(m+1, vector<ll>())); 
    fo(i, 1, n) {
        fo(j, 1, m) {
            cin >> mat[i][j];
        }
    } 
    fo(i, 1, n) {
        fo(j, 1, m) {
            int c;
            cin >> c;
            color[c].pb(mk(i, j));
        }
    } 

    precompute(); 
    while(q--) {
        int c1, c2;
        cin >> c1 >> c2;
        cout << get(c1, c2) << "\n";
    } 
}

/*
3 3 1
1000000000 1000000000 1000000000 
1000000000 1000000000 1000000000 
1000000000 1000000000 1000000000 
1 2 3  
4 5 6 
7 8 9
1 9
*/

Comments

Please read the guidelines before commenting.


There are no comments at the moment.