Advertisement
baka_mashiro

Untitled

Mar 19th, 2022
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <numeric>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <unordered_map>
  7. using namespace std;
  8. int main() {
  9.     //std::ios::sync_with_stdio(false);
  10.     int m, n, tmp;
  11.     cin >> m >> n;
  12.     unordered_map<int, vector<vector<int>>> map;
  13.     for (int i = 0; i < m; ++i)
  14.         for (int j = 0; j < n; ++j) {
  15.             cin >> tmp;
  16.             if (map.count(tmp) == 0) { map[tmp].resize(2); }
  17.             map[tmp][0].push_back(i);
  18.             map[tmp][1].push_back(j);
  19.         }
  20.     unsigned long long ans = 0;
  21.     for (auto vec : map) {
  22.         vector<int>& x = vec.second[0];
  23.         vector<int>& y = vec.second[1];
  24.         sort(x.begin(), x.end());
  25.         sort(y.begin(), y.end());
  26.         unordered_map<int, int> cntX, cntY;
  27.         for (int i = 0; i < x.size(); i++) {
  28.             cntX[x[i]]++;
  29.             cntY[y[i]]++;
  30.         }
  31.         auto ex = unique(x.begin(), x.end()) - x.begin();
  32.         auto ey = unique(y.begin(), y.end()) - y.begin();
  33.         vector<unsigned long long>
  34.             dx(ex - 1), dy(ey - 1),
  35.             leftX(ex),rightX(ex),
  36.             leftY(ey), rightY(ey),
  37.             nx(ex-1),ny(ey-1);
  38.  
  39.         for (int i = 1; i < ex; i++)
  40.             dx[i - 1] = x[i] - x[i - 1];
  41.         for (int i = 1; i < ey; i++)
  42.             dy[i - 1] = y[i] - y[i - 1];
  43.  
  44.         for (int i = 1; i < ex; ++i)
  45.             leftX[i] = leftX[i - 1] + cntX[x[i-1]];
  46.         for (int i = 1; i < ey; ++i)
  47.             leftY[i] = leftY[i - 1] + cntY[y[i-1]];
  48.  
  49.         for (int i = ex - 2; i >= 0; --i)
  50.             rightX[i] = rightX[i + 1] + cntX[x[i+1]];
  51.         for (int i = ey - 2; i >= 0; --i)
  52.             rightY[i] = rightY[i + 1] + cntY[y[i+1]];
  53.  
  54.         for (int i = 0; i < ex - 1; ++i)
  55.             nx[i] = leftX[i + 1] * rightX[i];
  56.         for (int i = 0; i < ey - 1; ++i)
  57.             ny[i] = leftY[i + 1] * rightY[i];
  58.        
  59.         unsigned long long xsum = 0, ysum = 0;
  60.         for (int i = 0; i < ex-1; ++i) {
  61.             xsum += (unsigned long long)nx[i] * (unsigned long long)dx[i];
  62.         }
  63.         for (int i = 0; i < ey-1; ++i) {
  64.             ysum += (unsigned long long)ny[i] * (unsigned long long)dy[i];
  65.         }
  66.         ans += xsum + ysum;
  67.     }
  68.  
  69.     cout << ans << endl;
  70.     return 0;
  71. }
  72.  
  73.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement