Submission #171020

#	Time	Username	Problem	Language	Result	Execution time	Memory
171020		talant117408	Star triangles (IZhO11_triangle)	C++17	0 / 100	2 ms	380 KiB

triangle

/*
    Code written by Talant I.D.
*/
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef tuple <int, int, int> tiii;
 
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define mt make_tuple
#define mod (int)1e9+7
#define eps (double)1e-9
#define PI 2*acos(-0.0);
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);
#define curMod 998244353

inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
 
bool isprime(int n){
	if(n < 2 || (n % 2 == 0 && n != 2))
		return false;
	for(int i = 3; i*i <= n; i += 2) 
		if(n % i == 0) return false;
	return true;
}

int main(){
    do_not_disturb
	int n, i;
	map <int, vector<int>> orderX, orderY;
	cin >> n;
	vector <pii> points(n+1);
	
	for(i = 1; i <= n; i++){
		cin >> points[i].first >> points[i].second;
	}
	sort(all(points));
	
	for(i = 1; i <= n; i++){
		int x = points[i].first, y = points[i].second;
		orderX[x].pb(y);
		orderY[y].pb(x);
	}
	
	ll sum = 0;
	for(i = 1; i <= n; i++){
		int x = points[i].first, y = points[i].second;
		auto it1 = lb(all(orderX[x]), y);
		auto it2 = lb(all(orderY[y]), x);
		ll d1 = distance(orderX[x].begin(), it1), d2 = distance(orderY[y].begin(), it2);
		sum += d1*d2;
		d1 = distance(orderX[x].begin(), it1), d2 = distance(it2+1, orderY[y].end());
		sum += d1*d2;
		d1 = distance(it1+1, orderX[x].end()), d2 = distance(orderY[y].begin(), it2);
		sum += d1*d2;
		d1 = distance(it1+1, orderX[x].end()), d2 = distance(it2+1, orderY[y].end());
		sum += d1*d2;
	}
	
	cout << sum;
	
    return 0;
} // What is to be written here?

• Subtask 1: 0 / 100