Submission #873993

#TimeUsernameProblemLanguageResultExecution timeMemory
873993The_SamuraiStar triangles (IZhO11_triangle)C++17
100 / 100
608 ms31096 KiB
// #pragma GCC optimize("Ofast,O3") // #pragma GCC target("avx,avx2") #include "bits/stdc++.h" using namespace std; using ll = long long; void solve() { int n; cin >> n; set<pair<int, int>> st; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; st.emplace(x, y); } ll ans = 0; map<int, vector<int>> mpx, mpy; for (auto [x, y]: st) { mpx[x].emplace_back(y); mpy[y].emplace_back(x); } for (auto &it: mpx) sort(it.second.begin(), it.second.end()); for (auto &it: mpy) sort(it.second.begin(), it.second.end()); for (auto [x, y]: st) { int px = upper_bound(mpx[x].begin(), mpx[x].end(), y) - mpx[x].begin(); int py = upper_bound(mpy[y].begin(), mpy[y].end(), x) - mpy[y].begin(); ans += 1ll * ((int) mpx[x].size() - px) * ((int) mpy[y].size() - py); ans += 1ll * (px - 1) * ((int) mpy[y].size() - py); ans += 1ll * ((int) mpx[x].size() - px) * (py - 1); ans += 1ll * (px - 1) * (py - 1); } cout << ans; } int main() { cin.tie(0)->sync_with_stdio(false); #ifdef sunnatov freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int q = 1; // cin >> q; while (q--) { solve(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...