oj.uz

Submission #173021

# Submission time Handle Problem Language Result Execution time Memory
173021 2020-01-03T05:03:59 Z tourist Star triangles (IZhO11_triangle) C++14
100 / 100
 592 ms 19396 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 3 ms 376 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 14 ms 1656 KB Output is correct
13 Correct 12 ms 1784 KB Output is correct
14 Correct 20 ms 2552 KB Output is correct
15 Correct 211 ms 10436 KB Output is correct
16 Correct 223 ms 10700 KB Output is correct
17 Correct 200 ms 10368 KB Output is correct
18 Correct 214 ms 10500 KB Output is correct
19 Correct 559 ms 18368 KB Output is correct
20 Correct 419 ms 14948 KB Output is correct
21 Correct 592 ms 19200 KB Output is correct
22 Correct 588 ms 19396 KB Output is correct