Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <string>
- #include <numeric>
- #include <vector>
- #include <algorithm>
- #include <unordered_map>
- using namespace std;
- int main() {
- //std::ios::sync_with_stdio(false);
- int m, n, tmp;
- cin >> m >> n;
- unordered_map<int, vector<vector<int>>> map;
- for (int i = 0; i < m; ++i)
- for (int j = 0; j < n; ++j) {
- cin >> tmp;
- if (map.count(tmp) == 0) { map[tmp].resize(2); }
- map[tmp][0].push_back(i);
- map[tmp][1].push_back(j);
- }
- unsigned long long ans = 0;
- for (auto vec : map) {
- vector<int>& x = vec.second[0];
- vector<int>& y = vec.second[1];
- sort(x.begin(), x.end());
- sort(y.begin(), y.end());
- unordered_map<int, int> cntX, cntY;
- for (int i = 0; i < x.size(); i++) {
- cntX[x[i]]++;
- cntY[y[i]]++;
- }
- auto ex = unique(x.begin(), x.end()) - x.begin();
- auto ey = unique(y.begin(), y.end()) - y.begin();
- vector<unsigned long long>
- dx(ex - 1), dy(ey - 1),
- leftX(ex),rightX(ex),
- leftY(ey), rightY(ey),
- nx(ex-1),ny(ey-1);
- for (int i = 1; i < ex; i++)
- dx[i - 1] = x[i] - x[i - 1];
- for (int i = 1; i < ey; i++)
- dy[i - 1] = y[i] - y[i - 1];
- for (int i = 1; i < ex; ++i)
- leftX[i] = leftX[i - 1] + cntX[x[i-1]];
- for (int i = 1; i < ey; ++i)
- leftY[i] = leftY[i - 1] + cntY[y[i-1]];
- for (int i = ex - 2; i >= 0; --i)
- rightX[i] = rightX[i + 1] + cntX[x[i+1]];
- for (int i = ey - 2; i >= 0; --i)
- rightY[i] = rightY[i + 1] + cntY[y[i+1]];
- for (int i = 0; i < ex - 1; ++i)
- nx[i] = leftX[i + 1] * rightX[i];
- for (int i = 0; i < ey - 1; ++i)
- ny[i] = leftY[i + 1] * rightY[i];
- unsigned long long xsum = 0, ysum = 0;
- for (int i = 0; i < ex-1; ++i) {
- xsum += (unsigned long long)nx[i] * (unsigned long long)dx[i];
- }
- for (int i = 0; i < ey-1; ++i) {
- ysum += (unsigned long long)ny[i] * (unsigned long long)dy[i];
- }
- ans += xsum + ysum;
- }
- cout << ans << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement