Submission #499047

#	Time	Username	Problem	Language	Result	Execution time	Memory
499047		ac2hu	Star triangles (IZhO11_triangle)	C++14	100 / 100	118 ms	3188 KiB

triangle

#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
int comp1[maxn];
int comp2[maxn];
signed main(){
	iostream::sync_with_stdio(false);
	cin.tie(nullptr);cout.tie(nullptr);
	int n;cin >> n;
	vector<pair<int,int>> stars(n);
	for(int i = 0;i<n;i++){
		cin >> stars[i].first >> stars[i].second;
	}
	sort(stars.begin(),stars.end());
	int c = 0;
	int k = stars[0].first;
	stars[0].first = 0;
	for(int i = 1;i<n;i++){
		if(stars[i].first != k){
			c++;
			k = stars[i].first;
		}
		stars[i].first = c;
	}
	sort(stars.begin(),stars.end(),[&](pair<int,int> a,pair<int,int> b){
		return a.second < b.second;
	});
	c = 0;
	k = stars[0].second;
	stars[0].second = 0;
	for(int i = 1;i<n;i++){
		if(stars[i].second != k){
			c++;
			k = stars[i].second;
		}
		stars[i].second = c;
	}	
	for(int i = 0;i<n;i++){
		comp1[stars[i].first]++;
		comp2[stars[i].second]++;
	}
	long long int ans = 0;
	for(int i = 0;i<n;i++){
		ans += 1ll*(comp1[stars[i].first] - 1)*(comp2[stars[i].second] - 1);
	}
	cout << ans << "\n";
}

• Subtask 1: 100 / 100