oj.uz

Submission #824554

# Submission time Handle Problem Language Result Execution time Memory
824554 2023-08-14T07:36:42 Z arush_agu Star triangles (IZhO11_triangle) C++17
100 / 100
 320 ms 25360 KB 
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

#ifdef DEBUG
#include <time.h>
#endif

#define all(a) (a).begin(), (a).end()
#define rev(a) (a).rbegin(), (a).rend()
#define F first
#define S second
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x)                                                                 \
  {                                                                            \
    ++recur_depth;                                                             \
    auto x_ = x;                                                               \
    --recur_depth;                                                             \
    cerr << string(recur_depth, '\t') << "\e[91m" << __func__ << ":"           \
         << __LINE__ << "\t" << #x << " = " << x_ << "\e[39m" << endl;         \
  }
#else
#define dbg(x)
#endif

using namespace std;
using namespace __gnu_pbds;

typedef pair<int, int> ii;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> llll;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pair<int, int>> vii;
typedef vector<vii> vvii;

typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pair<ll, ll>> vll;
typedef vector<vll> vvll;

typedef vector<bool> vb;

template <class type1>
using ordered_set = tree<type1, null_type, less<type1>, rb_tree_tag,
                         tree_order_statistics_node_update>;

template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
template <typename T_container, typename T = typename enable_if<
                                    !is_same<T_container, string>::value,
                                    typename T_container::value_type>::type>
ostream &operator<<(ostream &os, const T_container &v) {
  os << '{';
  string sep;
  for (const T &x : v)
    os << sep << x, sep = ", ";
  return os << '}';
}

const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 1e9;
const ld EPS = 1e-9;

void solve() {
  int n;
  cin >> n;
  vll a(n);
  for (auto &[x, y] : a)
    cin >> x >> y;

  sort(all(a));
  map<ll, vl> by_x, by_y;
  for (auto &[x, y] : a)
    by_y[y].push_back(x);
  sort(all(a), [&](llll a, llll b) {
    return llll{a.second, a.first} < llll{b.second, b.first};
  });
  for (auto &[x, y] : a)
    by_x[x].push_back(y);

  ll res = 0;
  for (auto &[x, y] : a)
    res += ((ll)by_x[x].size() - 1) * ((ll)by_y[y].size() - 1);
  cout << res << '\n';
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);

  clock_t start = clock();

  int test_cases = 1;
  // cin >> test_cases;

  while (test_cases--)
    solve();

#ifdef DEBUG
  cerr << fixed << setprecision(10)
       << "\nTime Taken: " << (double)(clock() - start) / CLOCKS_PER_SEC
       << "s\n";
#endif
  return 0;
}

Compilation message

triangle.cpp: In function 'int main()':
triangle.cpp:119:11: warning: unused variable 'start' [-Wunused-variable]
  119 |   clock_t start = clock();
      |           ^~~~~

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 280 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 328 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 6 ms 1876 KB Output is correct
13 Correct 5 ms 1868 KB Output is correct
14 Correct 9 ms 2508 KB Output is correct
15 Correct 104 ms 12040 KB Output is correct
16 Correct 106 ms 12620 KB Output is correct
17 Correct 114 ms 12120 KB Output is correct
18 Correct 100 ms 12100 KB Output is correct
19 Correct 282 ms 23864 KB Output is correct
20 Correct 210 ms 18800 KB Output is correct
21 Correct 320 ms 25360 KB Output is correct
22 Correct 303 ms 25312 KB Output is correct