oj.uz

Submission #21884

# Submission time Handle Problem Language Result Execution time Memory
21884 2017-04-26T16:02:09 Z ulna Star triangles (IZhO11_triangle) C++11
100 / 100
 769 ms 7132 KB 
#include <bits/stdc++.h>
using namespace std;

// why am I so weak

int n;
int x[300055], y[300055];

int main() {
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d %d", &x[i], &y[i]);
	}

	long long res = 0ll;

	vector<int> vec(n);

	for (int i = 0; i < n; i++) {
		vec[i] = i;
	}

	{
		// find bottom left
		sort(vec.begin(), vec.end(), [&] (int u, int v) {
			if (y[u] != y[v]) return y[u] > y[v];
			return x[u] > x[v];
		});

		map<int, int> c;

		int ac = 0;
		int last = -INT_MAX;

		for (auto u : vec) {
			if (y[u] != last) {
				ac = 0;
			}

			res += 1ll * ac * c[x[u]];

			c[x[u]]++;
			
			ac++;
			last = y[u];
		}
	}

	{
		// find bottom right
		sort(vec.begin(), vec.end(), [&] (int u, int v) {
			if (y[u] != y[v]) return y[u] > y[v];
			return x[u] < x[v];
		});

		map<int, int> c;

		int ac = 0;
		int last = -INT_MAX;

		for (auto u : vec) {
			if (y[u] != last) {
				ac = 0;
			}

			res += 1ll * ac * c[x[u]];

			c[x[u]]++;
			
			ac++;
			last = y[u];
		}
	}

	{
		// find top left
		sort(vec.begin(), vec.end(), [&] (int u, int v) {
			if (y[u] != y[v]) return y[u] < y[v];
			return x[u] > x[v];
		});

		map<int, int> c;

		int ac = 0;
		int last = -INT_MAX;

		for (auto u : vec) {
			if (y[u] != last) {
				ac = 0;
			}

			res += 1ll * ac * c[x[u]];

			c[x[u]]++;
			
			ac++;
			last = y[u];
		}
	}

	{
		// find top right
		sort(vec.begin(), vec.end(), [&] (int u, int v) {
			if (y[u] != y[v]) return y[u] < y[v];
			return x[u] < x[v];
		});

		map<int, int> c;

		int ac = 0;
		int last = -INT_MAX;

		for (auto u : vec) {
			if (y[u] != last) {
				ac = 0;
			}

			res += 1ll * ac * c[x[u]];

			c[x[u]]++;

			ac++;
			last = y[u];
		}
	}

	printf("%lld\n", res);

	return 0;
}

Compilation message

triangle.cpp: In function 'int main()':
triangle.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
triangle.cpp:13:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &x[i], &y[i]);
                               ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4376 KB Output is correct
2 Correct 0 ms 4376 KB Output is correct
3 Correct 0 ms 4376 KB Output is correct
4 Correct 0 ms 4376 KB Output is correct
5 Correct 0 ms 4376 KB Output is correct
6 Correct 0 ms 4376 KB Output is correct
7 Correct 0 ms 4376 KB Output is correct
8 Correct 0 ms 4376 KB Output is correct
9 Correct 0 ms 4376 KB Output is correct
10 Correct 0 ms 4376 KB Output is correct
11 Correct 0 ms 4376 KB Output is correct
12 Correct 6 ms 4376 KB Output is correct
13 Correct 6 ms 4640 KB Output is correct
14 Correct 19 ms 4772 KB Output is correct
15 Correct 273 ms 6220 KB Output is correct
16 Correct 296 ms 6256 KB Output is correct
17 Correct 219 ms 6220 KB Output is correct
18 Correct 229 ms 6220 KB Output is correct
19 Correct 756 ms 7048 KB Output is correct
20 Correct 449 ms 6744 KB Output is correct
21 Correct 729 ms 7132 KB Output is correct
22 Correct 769 ms 7132 KB Output is correct