Submission #207029

#	Time	Username	Problem	Language	Result	Execution time	Memory
207029		pavement	Star triangles (IZhO11_triangle)	C++17	0 / 100	2093 ms	25080 KiB

triangle

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

int N, C, X[300005], Y[300005];
map<int, vector<int> > XC, YC;

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> X[i] >> Y[i];
		XC[X[i]].push_back(Y[i]);
		YC[Y[i]].push_back(X[i]);
	}
	for (auto &i : XC) sort(i.second.begin(), i.second.end());
	for (auto &i : YC) sort(i.second.begin(), i.second.end());
	for (int i = 1; i <= N; i++) {
		auto it = upper_bound(YC[Y[i]].begin(), YC[Y[i]].end(), X[i]), it2 = upper_bound(XC[X[i]].begin(), XC[X[i]].end(), Y[i]);
		C += (YC[Y[i]].size() - (it - YC[Y[i]].begin())) * (XC[X[i]].size() - (it2 - XC[X[i]].begin()));
	}
	for (int i = 1; i <= N; i++) {
		auto it = upper_bound(YC[Y[i]].begin(), YC[Y[i]].end(), X[i]), it2 = lower_bound(XC[X[i]].begin(), XC[X[i]].end(), Y[i]);
		C += (YC[Y[i]].size() - (it - YC[Y[i]].begin())) * (it2 - XC[X[i]].begin());
	}
	for (int i = 1; i <= N; i++) {
		auto it = lower_bound(YC[Y[i]].begin(), YC[Y[i]].end(), X[i]), it2 = upper_bound(XC[X[i]].begin(), XC[X[i]].end(), Y[i]);
		C += (it - YC[Y[i]].begin()) * (XC[X[i]].size() - (it2 - XC[X[i]].begin()));
	}
	for (int i = 1; i <= N; i++) {
		auto it = lower_bound(YC[Y[i]].begin(), YC[Y[i]].end(), X[i]), it2 = lower_bound(XC[X[i]].begin(), XC[X[i]].end(), Y[i]);
		C += (it - YC[Y[i]].begin()) * (it2 - XC[X[i]].begin());
	}
	cout << C << '\n';
}

Compilation message (stderr)

triangle.cpp:8:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• Subtask 1: 0 / 100