Submission #995154

#TimeUsernameProblemLanguageResultExecution timeMemory
995154Sokol080808Star triangles (IZhO11_triangle)C++17
100 / 100
783 ms22944 KiB
#include <bits/stdc++.h> #include <malloc.h> using namespace std; #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() typedef long long ll; typedef unsigned long long ull; typedef long double ld; signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // #ifndef ONPC // freopen("triangles.in", "r", stdin); // freopen("triangles.out", "w", stdout); // #endif int n; cin >> n; vector<array<int, 2>> a(n); map<int, vector<int>> x, y; for (int i = 0; i < n; i++) { cin >> a[i][0] >> a[i][1]; y[a[i][0]].push_back(a[i][1]); x[a[i][1]].push_back(a[i][0]); } set<int> ok_x, ok_y; for (int i = 0; i < n; i++) { if (!ok_x.count(a[i][0])) { ok_x.insert(a[i][0]); sort(all(y[a[i][0]])); } if (!ok_y.count(a[i][1])) { ok_y.insert(a[i][1]); sort(all(x[a[i][1]])); } } ll ans = 0; for (int i = 0; i < n; i++) { auto [curx, cury] = a[i]; ll u = y[curx].end() - upper_bound(all(y[curx]), cury); ll d = lower_bound(all(y[curx]), cury) - y[curx].begin(); ll l = lower_bound(all(x[cury]), curx) - x[cury].begin(); ll r = x[cury].end() - upper_bound(all(x[cury]), curx); ans += (u + d) * (l + r); } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...