oj.uz

Submission #207029

# Submission time Handle Problem Language Result Execution time Memory
207029 2020-03-06T06:50:16 Z pavement Star triangles (IZhO11_triangle) C++17
0 / 100
 2000 ms 25080 KB 
#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

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

Subtask #1
0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 380 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 6 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 6 ms 504 KB Output is correct
11 Correct 7 ms 504 KB Output is correct
12 Correct 34 ms 1912 KB Output is correct
13 Correct 32 ms 1912 KB Output is correct
14 Correct 48 ms 2680 KB Output is correct
15 Correct 727 ms 12536 KB Output is correct
16 Correct 799 ms 13208 KB Output is correct
17 Correct 740 ms 12536 KB Output is correct
18 Correct 734 ms 12536 KB Output is correct
19 Execution timed out 2093 ms 25080 KB Time limit exceeded
20 Halted 0 ms 0 KB -