Submission #739446

#	Time	Username	Problem	Language	Result	Execution time	Memory
739446		MODDI	Star triangles (IZhO11_triangle)	C++14	100 / 100	495 ms	16120 KiB

triangle

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n;
vector<pair<int, pll> > arr;
map<ll,ll> hor, ver;
bool comp1(pair<int, pll>& a, pair<int, pll>& b){
	if(a.second.first < b.second.first)	return true;
	else if(a.second.first > b.second.first)	return false;
	else{
		if(a.second.second < b.second.second)	return true;
		return false;
	}
}
bool comp2(pair<int, pll>& a, pair<int, pll>& b){
	if(a.second.second < b.second.second) return true;
	else if(a.second.second > b.second.second)	return false;
	else{
		if(a.second.first < b.second.first)	return true;
		return false;
	}
}
int main(){
	cin>>n;
	for(int i = 0; i < n; i++){
		int a, b;
		cin>>a>>b;
		a += 1e9;
		b += 1e9;
		arr.pb(mp(i, mp(a,b)));
	}
	sort(arr.begin(), arr.end(), comp1);
	int cnt_hor[n], cnt_ver[n];
	memset(cnt_hor, 0, sizeof cnt_hor);
	memset(cnt_ver, 0, sizeof cnt_ver);
	for(int i = 0; i < n; i++){
		ver[arr[i].second.first]++;
		hor[arr[i].second.second]++;
	}
	sort(arr.begin(), arr.end(), comp2);
	for(int i = 0; i < n; i++){
		cnt_hor[i] = hor[arr[i].second.second];
		cnt_ver[i] = ver[arr[i].second.first];
	}
	ll ans = 0;
	for(int i = 0; i < n; i++){
//		cout<<cnt_hor[i]<<" "<<cnt_ver[i]<<endl;
		ans += (cnt_hor[i]-1) * (cnt_ver[i]-1);
	}
	cout<<ans<<endl;
	return 0;
}

• Subtask 1: 100 / 100