Submission #45966

#	Time	Username	Problem	Language	Result	Execution time	Memory
45966		ernestvw	별들과 삼각형 (IZhO11_triangle)	C++11	0 / 100	13 ms	16168 KiB

triangle

#include <bits/stdc++.h>
using namespace std;

// cartesian tree
/*#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pd_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> Tree;
*/

// pragma
/*#pragma GCC optimize("O3")
#pragma GCC target("sse4")
*/

// defines
#define int long long
#define double long double
#define pb push_back
#define FOR(i, a, b) for(int i=a;i<(b);i++)
#define FORD(i, a, b) for(int i=(b)-1;i>=a;i--)
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

// consts
const int MOD = 1e9+7;
const int oo = 1e9;
const int OO = 1e18;
const double eps = 1e-9;
const double PI = 4.0 * atan(1.0);

void solve();

signed main() {
	fast_io();
	solve();
	return 0;
}

////////////////////42////////////////////

int n, X[400000], Y[400000];
map<int, int> comprimer, decomprimer;
int cntX[1000*1000],cntY[1000*1000];

void compress(){
	set<int> vals;
	for(int i=0;i<n;i++)vals.insert(X[i]),vals.insert(Y[i]);
	int cnt=0;
	for(auto it=vals.begin();it!=vals.end();it++){
		comprimer[cnt]=*it;
		decomprimer[*it]=cnt;
		cnt++;
	}
	for(int i=0;i<n;i++){
		X[i]=comprimer[X[i]];
		Y[i]=comprimer[Y[i]];
	}
}

void solve() {
	cin>>n;
	for(int i=0;i<n;i++)cin>>X[i]>>Y[i];
	fill_n(cntX, 1000*1000, 0);
	fill_n(cntY, 1000*1000, 0);
	compress();
	set<pair<int, int>> pts;
	for(int i=0;i<n;i++){
		if(pts.find({X[i],Y[i]})!=pts.end())
			continue;
		pts.insert({X[i],Y[i]});
		cntX[X[i]]++;
		cntY[Y[i]]++;
	}
	int total=0;
	for(int i=0;i<n;i++)
		total+=(cntX[X[i]]-1LL)*(cntY[Y[i]]-1LL);
	cout<<total<<endl;
}

• Subtask 1: 0 / 100