Submission #173021

#	Time	Username	Problem	Language	Result	Execution time	Memory
173021		tourist	Star triangles (IZhO11_triangle)	C++14	100 / 100	592 ms	19396 KiB

triangle

#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>

using namespace std;

#define ll long long
#define sz(x) (int)x.size()
#define pii pair < int, int >
#define endl "\n"
#define METH ios::sync_with_stdio(0); cin.tie(0);
#define BEGIN cout << "BEGIN" << endl;
#define END cout << "END" << endl;

const int mod = 1e9 + 7;															/// ANOTHER HASH MOD: 228228227
const int prime = 29;																	/// ANOTHER HASH PRIME: 997
const int INF = ((long long) 0xCAFEBABE - 1e9 - 4e8);

int n;
map < int, vector < int > > x, y;
vector < pii > v;

inline void read() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		v.push_back({a, b});
	}
}

ll calc(int i) {
	int a = v[i - 1].first;
	int b = v[i - 1].second;
	int index1 = lower_bound(y[a].begin(), y[a].end(), b) - y[a].begin();
	int index2 = lower_bound(x[b].begin(), x[b].end(), a) - x[b].begin();
	return (y[a].size() - 1) * (x[b].size() - 1);
}

inline void solve() {
	sort(v.begin(), v.end());
	for (int i = 0; i < n; i++) {
		int a = v[i].first, b = v[i].second;
		y[a].push_back(b);
		x[b].push_back(a);
	}
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans += calc(i);
	}

	cout << ans << endl;
}

int main() {
	int t = 1;

	while (t--) {
		read();
		solve();
	}
}

	

Compilation message (stderr)

triangle.cpp: In function 'long long int calc(int)':
triangle.cpp:37:6: warning: unused variable 'index1' [-Wunused-variable]
  int index1 = lower_bound(y[a].begin(), y[a].end(), b) - y[a].begin();
      ^~~~~~
triangle.cpp:38:6: warning: unused variable 'index2' [-Wunused-variable]
  int index2 = lower_bound(x[b].begin(), x[b].end(), a) - x[b].begin();
      ^~~~~~
triangle.cpp: In function 'void read()':
triangle.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
triangle.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100