oj.uz

Submission #683269

# Submission time Handle Problem Language Result Execution time Memory
683269 2023-01-18T05:31:06 Z vovamr Star triangles (IZhO11_triangle) C++17
100 / 100
 758 ms 20268 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

inline void solve() {
	int n;
	cin >> n;
	ve<pii> a(n);
	for (auto &[x, y] : a) cin >> x >> y;

	map<int,ve<int>> X, Y;
	for (auto &[x, y] : a) X[x].pb(y), Y[y].pb(x);
	for (auto &[x, vec] : X) sort(all(vec));
	for (auto &[y, vec] : Y) sort(all(vec));

	ll ans = 0;
	for (auto &[x, y] : a) {
		int right_x = sz(Y[y]) - (upper_bound(all(Y[y]), x) - Y[y].begin());
		int left_x = sz(Y[y]) - right_x - 1;

		int right_y = sz(X[x]) - (upper_bound(all(X[x]), y) - X[x].begin());
		int left_y = sz(X[x]) - right_y - 1;

		for (auto f : {right_x, left_x}) {
			for (auto s : {right_y, left_y}) {
				ans += f * 1ll * s;
			}
		}
	}
	cout << ans;
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 320 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 328 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 14 ms 1644 KB Output is correct
13 Correct 11 ms 1640 KB Output is correct
14 Correct 18 ms 2488 KB Output is correct
15 Correct 228 ms 10412 KB Output is correct
16 Correct 261 ms 10888 KB Output is correct
17 Correct 204 ms 10316 KB Output is correct
18 Correct 208 ms 10300 KB Output is correct
19 Correct 713 ms 19116 KB Output is correct
20 Correct 462 ms 15388 KB Output is correct
21 Correct 690 ms 20268 KB Output is correct
22 Correct 758 ms 20196 KB Output is correct