Submission #678656

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
678656	2023-01-06T09:40:59 Z	yellowtoad	Star triangles (IZhO11_triangle)	C++17	100 / 100	272 ms	18388 KB

triangle

#include <iostream>
#include <vector>
using namespace std;

const long long int mod = 1e5+7;
long long int n, x, y, ans;
pair<long long int, long long int> a[3000100];
vector<pair<long long int,long long int>> hx[mod+10], hy[mod+10];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].first >> a[i].second;
		for (int j = 0; j < hx[((a[i].first%mod)+mod)%mod].size(); j++) {
			if (hx[((a[i].first%mod)+mod)%mod][j].first == a[i].first) {
				hx[((a[i].first%mod)+mod)%mod][j].second++;
				goto skip;
			}
		}
		hx[((a[i].first%mod)+mod)%mod].push_back({a[i].first,1});
		skip:;
		for (int j = 0; j < hy[((a[i].second%mod)+mod)%mod].size(); j++) {
			if (hy[((a[i].second%mod)+mod)%mod][j].first == a[i].second) {
				hy[((a[i].second%mod)+mod)%mod][j].second++;
				goto skipp;
			}
		}
		hy[((a[i].second%mod)+mod)%mod].push_back({a[i].second,1});
		skipp:;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < hx[((a[i].first%mod)+mod)%mod].size(); j++) {
			if (hx[((a[i].first%mod)+mod)%mod][j].first == a[i].first) {
				x = hx[((a[i].first%mod)+mod)%mod][j].second;
				goto skippp;
			}
		}
		skippp:;
		for (int j = 0; j < hy[((a[i].second%mod)+mod)%mod].size(); j++) {
			if (hy[((((a[i].second%mod)+mod)%mod)+mod)%mod][j].first == a[i].second) {
				y = hy[((a[i].second%mod)+mod)%mod][j].second;
				goto skipppp;
			}
		}
		skipppp:;
		ans += (x-1)*(y-1);
	}
	cout << ans << endl;
}

Compilation message

triangle.cpp: In function 'int main()':
triangle.cpp:14:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for (int j = 0; j < hx[((a[i].first%mod)+mod)%mod].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triangle.cpp:22:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for (int j = 0; j < hy[((a[i].second%mod)+mod)%mod].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triangle.cpp:32:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for (int j = 0; j < hx[((a[i].first%mod)+mod)%mod].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
triangle.cpp:39:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |   for (int j = 0; j < hy[((a[i].second%mod)+mod)%mod].size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	4984 KB	Output is correct
4	Correct	3 ms	4948 KB	Output is correct
5	Correct	3 ms	4948 KB	Output is correct
6	Correct	4 ms	4948 KB	Output is correct
7	Correct	3 ms	5012 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	4 ms	4948 KB	Output is correct
10	Correct	3 ms	5008 KB	Output is correct
11	Correct	4 ms	5016 KB	Output is correct
12	Correct	10 ms	5532 KB	Output is correct
13	Correct	12 ms	5588 KB	Output is correct
14	Correct	12 ms	5916 KB	Output is correct
15	Correct	93 ms	10556 KB	Output is correct
16	Correct	100 ms	10968 KB	Output is correct
17	Correct	111 ms	10660 KB	Output is correct
18	Correct	105 ms	10536 KB	Output is correct
19	Correct	246 ms	17296 KB	Output is correct
20	Correct	177 ms	14392 KB	Output is correct
21	Correct	262 ms	18124 KB	Output is correct
22	Correct	272 ms	18388 KB	Output is correct