2201.cpp (1086B)
1 class Solution { 2 public: 3 int digArtifacts(int n, const vector<vector<int>> &artifacts, const vector<vector<int>> &dig) const { 4 vector<vector<int>> grid(n, vector(n, 0)); 5 for (const auto &d : dig) 6 grid[d[0]][d[1]] = 1; 7 8 for (int i = 0, acc = 0; i < n; i++) 9 grid[i][0] = acc += grid[i][0]; 10 for (int i = 0, acc = 0; i < n; i++) 11 grid[0][i] = acc += grid[0][i]; 12 for (int i = 1; i < n; i++) { 13 for (int j = 1; j < n; j++) { 14 grid[i][j] += grid[i - 1][j] + grid[i][j - 1] - grid[i - 1][j - 1]; 15 } 16 } 17 18 int res = 0; 19 for (const auto &art : artifacts) { 20 const int goal = (art[2] - art[0] + 1) * (art[3] - art[1] + 1); 21 int crnt = grid[art[2]][art[3]]; 22 crnt -= art[0] > 0 ? grid[art[0] - 1][art[3]] : 0; 23 crnt -= art[1] > 0 ? grid[art[2]][art[1] - 1] : 0; 24 crnt += art[0] > 0 && art[1] > 0 ? grid[art[0] - 1][art[1] - 1] : 0; 25 res += goal == crnt; 26 } 27 28 return res; 29 } 30 };