oj.uz

Submission #867668

# Submission time Handle Problem Language Result Execution time Memory
867668 2023-10-29T05:59:48 Z sleepntsheep Star triangles (IZhO11_triangle) C++17
100 / 100
 174 ms 13396 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][2];
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) ++b[a[i][j] = lower_bound(c, c+C, a[i][j]) - c][j];
    sort(a, a+n);
    for (ll e = 0, d = 0, i = 0, l = -1; i < n; ++i)
    {
        if (a[i] == a[i+1]) continue;
        if (a[i][0] != l) l = a[i][0], d = 0, e = 0;
        z += d + (b[a[i][1]][1] - 1ll) * e;
        ++e, d += b[a[i][1]][1] - 1;
    }
    cout << z;
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 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 0 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 2396 KB Output is correct
10 Correct 1 ms 2516 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 2652 KB Output is correct
14 Correct 6 ms 2888 KB Output is correct
15 Correct 66 ms 7660 KB Output is correct
16 Correct 62 ms 7916 KB Output is correct
17 Correct 60 ms 7508 KB Output is correct
18 Correct 57 ms 7468 KB Output is correct
19 Correct 162 ms 12860 KB Output is correct
20 Correct 122 ms 10504 KB Output is correct
21 Correct 173 ms 13396 KB Output is correct
22 Correct 174 ms 13284 KB Output is correct