oj.uz

Submission #585446

# Submission time Handle Problem Language Result Execution time Memory
585446 2022-06-29T01:25:32 Z Shin Star triangles (IZhO11_triangle) C++14
100 / 100
 367 ms 53972 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()

using namespace std;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

const int N = 6e5 + 7;
int n;
int x[N];
int y[N];
pair<int, int> a[N];
map<int, int> cnt[N];

signed main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  vector<int> val;
  for (int i = 1; i <= n; i ++) {
    cin >> a[i].fi >> a[i].se;
    val.push_back(a[i].fi);
    val.push_back(a[i].se);
  }
  sort(all(val));
  val.erase(unique(all(val)), val.end());
  for (int i = 1; i <= n; i ++) {
    a[i].fi = lower_bound(all(val), a[i].fi) - val.begin();
    a[i].se = lower_bound(all(val), a[i].se) - val.begin();
    x[a[i].fi] ++;
    y[a[i].se] ++;
    cnt[a[i].fi][a[i].se] ++;
  }
  long long res = 0;
  for (int i = 1; i <= n; i ++) {
    int hors = x[a[i].fi] - cnt[a[i].fi][a[i].se];
    int vers = y[a[i].se] - cnt[a[i].fi][a[i].se];
    res += 1LL * cnt[a[i].fi][a[i].se] * hors * vers;
  }
  cout << res;
  return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 28500 KB Output is correct
2 Correct 14 ms 28452 KB Output is correct
3 Correct 14 ms 28508 KB Output is correct
4 Correct 14 ms 28500 KB Output is correct
5 Correct 14 ms 28492 KB Output is correct
6 Correct 15 ms 28504 KB Output is correct
7 Correct 14 ms 28536 KB Output is correct
8 Correct 15 ms 28524 KB Output is correct
9 Correct 14 ms 28484 KB Output is correct
10 Correct 15 ms 28564 KB Output is correct
11 Correct 14 ms 28616 KB Output is correct
12 Correct 26 ms 29312 KB Output is correct
13 Correct 25 ms 29436 KB Output is correct
14 Correct 23 ms 29396 KB Output is correct
15 Correct 90 ms 37180 KB Output is correct
16 Correct 97 ms 37936 KB Output is correct
17 Correct 95 ms 37128 KB Output is correct
18 Correct 93 ms 37240 KB Output is correct
19 Correct 292 ms 52124 KB Output is correct
20 Correct 195 ms 45504 KB Output is correct
21 Correct 367 ms 53920 KB Output is correct
22 Correct 329 ms 53972 KB Output is correct