답안 #499047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
499047	2021-12-27T06:27:58 Z	ac2hu	별들과 삼각형 (IZhO11_triangle)	C++14	100 / 100	118 ms	3188 KB

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.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	204 KB	Output is correct
4	Correct	0 ms	324 KB	Output is correct
5	Correct	0 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	0 ms	204 KB	Output is correct
8	Correct	1 ms	204 KB	Output is correct
9	Correct	1 ms	320 KB	Output is correct
10	Correct	1 ms	312 KB	Output is correct
11	Correct	1 ms	324 KB	Output is correct
12	Correct	3 ms	588 KB	Output is correct
13	Correct	3 ms	644 KB	Output is correct
14	Correct	4 ms	584 KB	Output is correct
15	Correct	36 ms	1604 KB	Output is correct
16	Correct	46 ms	1664 KB	Output is correct
17	Correct	38 ms	1512 KB	Output is correct
18	Correct	39 ms	1504 KB	Output is correct
19	Correct	99 ms	2900 KB	Output is correct
20	Correct	75 ms	2412 KB	Output is correct
21	Correct	118 ms	3188 KB	Output is correct
22	Correct	112 ms	3188 KB	Output is correct