oj.uz

Submission #1100628

# Submission time Handle Problem Language Result Execution time Memory
1100628 2024-10-14T10:44:46 Z vjudge1 Star triangles (IZhO11_triangle) C++17
100 / 100
 236 ms 22412 KB 
//#include <bits/stdc++.h>

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <random>


using namespace std;
using ll = long long;

#define int long long

const int N = 6e5 + 7;
const int M = 1e9 + 7;

struct custom_hash { //unordered_map<long long, int, custom_hash> safe_map; gp_hash_table<long long, int, custom_hash> safe_hash_table;

    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

int binpow(int a, int n, int m) {
    int res = 1;
    while (n) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}

/*inline void factorials(int n) {
    f[0] = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = (f[i - 1] * i) % M;
    }
    invf[n] = binpow(f[n], M - 2, M);
    for(int i = n - 1; i >= 0; i--) {
        invf[i] = (invf[i + 1] * (i + 1)) % M;
    }
}

inline int cnk(int n, int k) {
    if(k > n) {
        return 0;
    }
    return (((f[n] * invf[n - k]) % M) * invf[k]) % M;
} */

int a[N], b[N], c[N];
set<int> ms;
int xx[N], yy[N];
vector<pair<int, int>> vv, uu;
unordered_map<int, int, custom_hash> mp, mp2, val;

inline void Solve() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        vv.push_back({x, y});
        uu.push_back({y, x});
        ms.insert(x);
        ms.insert(y);
    }
    
    sort(vv.begin(), vv.end());
    sort(uu.begin(), uu.end());
    
    int nw = 1;
    for(auto to : ms) {
        val[to] = nw;
        nw++;
    }
    for(int i = 1; i <= n; i++) {
        xx[val[vv[i - 1].first]]++;
        yy[val[vv[i - 1].second]]++;
    }
    
    int ans = 0;
    
    for(int i = 0; i < n; i++) {
        ans += (yy[val[vv[i].second]] - 1) * (xx[val[vv[i].first]] - 1);
    }
    //cout << val[vv[1ll].first] << ' ';
    //cout << ans << ' ';
    for(int i = 0; i < n; i++) {
        ans += (xx[val[uu[i].second]] - 1) * (yy[val[uu[i].first]] - 1);
    }
    cout << ans / 2;
}

signed main() {
    //freopen("brackets.in", "r", stdin);
    //freopen("brackets.out", "w", stdout);
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    //cout << '\n' << '\n';
    
    while(t--) {
        Solve();
    }
    
    return 0;
}

/*
 Special cases n = 1 or just 1?
 u r using unsigned long long which can't carry negative values?
 what if u r doing the same thing n times, it may cause the TL
 make sure that the size of your massives, vectors are enough
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 2 ms 4432 KB Output is correct
4 Correct 1 ms 4432 KB Output is correct
5 Correct 1 ms 4432 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 2 ms 4432 KB Output is correct
10 Correct 2 ms 4688 KB Output is correct
11 Correct 2 ms 4688 KB Output is correct
12 Correct 9 ms 5960 KB Output is correct
13 Correct 8 ms 5960 KB Output is correct
14 Correct 12 ms 6472 KB Output is correct
15 Correct 79 ms 14120 KB Output is correct
16 Correct 93 ms 14116 KB Output is correct
17 Correct 83 ms 14100 KB Output is correct
18 Correct 76 ms 14128 KB Output is correct
19 Correct 205 ms 22412 KB Output is correct
20 Correct 147 ms 18200 KB Output is correct
21 Correct 236 ms 22280 KB Output is correct
22 Correct 220 ms 22284 KB Output is correct