oj.uz

Submission #867670

# Submission time Handle Problem Language Result Execution time Memory
867670 2023-10-29T06:01:08 Z sleepntsheep Star triangles (IZhO11_triangle) C++17
100 / 100
 175 ms 6992 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>

using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 300005

int n, c[N<<1], C, b[N<<1];
array<int, 2> a[N]; ll z;

int main()
{
    ShinLena;
    for (int i = (cin >> n, 0); i < n; ++i) cin >> a[i][0] >> a[i][1], c[C++] = a[i][0], c[C++] = a[i][1];
    sort(c, c+C); C = unique(c, c+C) - c;
    for (int i = 0; i < n; ++i) 
    {
        for (int j = 0; j < 2; ++j) a[i][j] = lower_bound(c, c+C, a[i][j]) - c;
        ++b[a[i][1]];
    }
    sort(a, a+n); n = unique(a, a+n) - a;
    for (ll e = 0, d = 0, i = 0, l = -1; i < n; ++i)
    {
        if (a[i][0] != l) l = a[i][0], d = 0, e = 0;
        z += d + (b[a[i][1]] - 1ll) * e;
        ++e, d += b[a[i][1]] - 1;
    }
    cout << z;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 0 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 0 ms 2396 KB Output is correct
7 Correct 0 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 5 ms 2652 KB Output is correct
13 Correct 5 ms 2672 KB Output is correct
14 Correct 5 ms 2576 KB Output is correct
15 Correct 56 ms 5524 KB Output is correct
16 Correct 66 ms 5716 KB Output is correct
17 Correct 56 ms 5500 KB Output is correct
18 Correct 56 ms 5460 KB Output is correct
19 Correct 159 ms 6732 KB Output is correct
20 Correct 118 ms 6228 KB Output is correct
21 Correct 175 ms 6936 KB Output is correct
22 Correct 171 ms 6992 KB Output is correct