Submission #207031

#	Time	Username	Problem	Language	Result	Execution time	Memory
207031		pavement	Star triangles (IZhO11_triangle)	C++17	100 / 100	337 ms	48248 KiB

triangle

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

int N, C, X[300005], Y[300005], CX[300005], CY[300005];
pair<int, int> TX[300005], TY[300005];
vector<int> XC[300005], YC[300005];

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

Compilation message (stderr)

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

• Subtask 1: 100 / 100