Submission #873993

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
873993	2023-11-16 06:59:41	The_Samurai	Star triangles (IZhO11_triangle)	C++17	100 / 100	608 ms	31096 KiB

triangle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// #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);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 100 / 100