Submission #357374

# Submission time Handle Problem Language Result Execution time Memory
357374 2021-01-24T04:21:39 Z LastRonin Star triangles (IZhO11_triangle) C++14
100 / 100
1014 ms 35548 KB
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
#define ld long double
using namespace std;
 
const ll N = 4e5 + 10;
const ll M = 1e3 + 10;
const ll big = 1e9;
const ll hsh2 = 1964325029;
const ll wp = 491;
const long long mod = 1e9 + 7;
const long double EPS = 1e-14;
const ll block = 1e7;
const ll shift = 2e3;
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());

ll n, x[N], y[N];

vector<ll> z, z2;

ll f[N], k[N];
map<pill, ll> cnt;
int main() {
	speed;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
		z.pb(x[i]), z2.pb(y[i]);
	}
	sort(all(z)), sort(all(z2));
	z.erase(unique(all(z)), z.end()), z2.erase(unique(all(z2)), z2.end());
	for(int i = 1; i <= n; i++) {
    	x[i] = lower_bound(all(z), x[i]) - z.begin();
    	y[i] = lower_bound(all(z2), y[i]) - z2.begin();
		f[x[i]]++;
		k[y[i]]++;
		cnt[mp(x[i], y[i])]++;		
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
    	ll b = cnt[mp(x[i], y[i])];
		ans += (f[x[i]] - b) * (k[y[i]] - b);
    }
    cout << ans;
}                     
/*
AAAACACA
*/
# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 10 ms 1644 KB Output is correct
13 Correct 10 ms 1644 KB Output is correct
14 Correct 12 ms 1772 KB Output is correct
15 Correct 219 ms 12380 KB Output is correct
16 Correct 255 ms 13528 KB Output is correct
17 Correct 206 ms 12376 KB Output is correct
18 Correct 182 ms 12376 KB Output is correct
19 Correct 858 ms 33124 KB Output is correct
20 Correct 586 ms 24060 KB Output is correct
21 Correct 1014 ms 35532 KB Output is correct
22 Correct 870 ms 35548 KB Output is correct