oj.uz

Submission #739446

# Submission time Handle Problem Language Result Execution time Memory
739446 2023-05-10T13:16:52 Z MODDI Star triangles (IZhO11_triangle) C++14
100 / 100
 495 ms 16120 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 300 KB Output is correct
9 Correct 1 ms 304 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 11 ms 1396 KB Output is correct
13 Correct 12 ms 1460 KB Output is correct
14 Correct 16 ms 1888 KB Output is correct
15 Correct 161 ms 9396 KB Output is correct
16 Correct 166 ms 9820 KB Output is correct
17 Correct 167 ms 9408 KB Output is correct
18 Correct 170 ms 9436 KB Output is correct
19 Correct 448 ms 15532 KB Output is correct
20 Correct 336 ms 12876 KB Output is correct
21 Correct 456 ms 16120 KB Output is correct
22 Correct 495 ms 15976 KB Output is correct