Submission #30873

#	Time	Username	Problem	Language	Result	Execution time	Memory
30873		Navick	Star triangles (IZhO11_triangle)	C++14	100 / 100	663 ms	9908 KiB

triangle

#include <bits/stdc++.h>
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 3e5 + 10;

int x[N], y[N], dx[N], dy[N];
map<int, int> mx, my;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	for(int i=0; i<n; i++){
		cin >> x[i] >> y[i];
		mx[x[i]] = my[y[i]] = 0;
	}

	int cnt = 0;
	for(auto X : mx)
		mx[X.F] = cnt++;
	cnt = 0;
	for(auto Y : my)
		my[Y.F] = cnt++;

	for(int i=0; i<n; i++){
		x[i] = mx[x[i]];
		y[i] = my[y[i]];
		dx[x[i]]++;
		dy[y[i]]++;
	}
	ll ans = 0;

	for(int i=0; i<n; i++)
		ans += 1LL * (dx[x[i]] - 1) * (dy[y[i]] - 1);
	cout << ans << endl;
}

• Subtask 1: 100 / 100