62162023-11-08 10:27:37EsVagyCsodálatos Csillagképekcpp17Time limit exceeded 65/1001.083s89656 KiB
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>

using namespace std;

struct star
{
	int x, y;
};

int main()
{
	map<int, set<int>> rows;
	map<int, set<int>> cols;
	vector<star> stars;

	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		star s;
		cin >> s.x >> s.y;

		stars.push_back(s);

		if (rows.count(s.y) == 0)
		{
			rows.insert(make_pair(s.y, set<int>()));
		}
		rows[s.y].insert(s.x);

		if (cols.count(s.x) == 0)
		{
			cols.insert(make_pair(s.x, set<int>()));
		}
		cols[s.x].insert(s.y);
	}

	long int ans = 0;

	for (star s : stars)
	{
		set<int>::iterator ix = rows[s.y].find(s.x);
		int x = distance(rows[s.y].begin(), ix);
		int up = x;
		int down = rows[s.y].size() - x - 1;

		set<int>::iterator iy = cols[s.x].find(s.y);
		int y = distance(cols[s.x].begin(), iy);
		int left = y;
		int right = cols[s.x].size() - y - 1;

		ans += up * right;
		ans += left * up;
		ans += down * left;
		ans += right * down;
	}

	cout << ans << "\n";
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1940 KiB
subtask225/25
2Accepted3ms2136 KiB
3Accepted3ms2344 KiB
4Accepted3ms2464 KiB
5Accepted3ms2560 KiB
subtask340/40
6Accepted4ms2976 KiB
7Accepted4ms3236 KiB
8Accepted4ms3460 KiB
9Accepted4ms3460 KiB
10Accepted4ms3408 KiB
11Accepted6ms3648 KiB
subtask40/35
12Accepted307ms14312 KiB
13Time limit exceeded1.024s89656 KiB
14Accepted397ms49608 KiB
15Accepted601ms20764 KiB
16Time limit exceeded1.034s28404 KiB
17Accepted652ms73904 KiB
18Accepted182ms30088 KiB
19Time limit exceeded1.083s19752 KiB
20Accepted864ms88832 KiB
21Time limit exceeded1.049s47908 KiB