oj.uz

Submission #357379

# Submission time Handle Problem Language Result Execution time Memory
357379 2021-01-24T04:23:01 Z LastRonin Star triangles (IZhO11_triangle) C++11
100 / 100
 825 ms 29124 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define mp make_pair
#define si short int
#define speed ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pill pair<ll,ll>
#define f first
#define s second
#define pilc pair<ll,char>
#define all(a) (a).begin(),(a).end()
#define rep(s,e,step) for(int i = (s); i < (e) ; i += step)
#define vrep(s,e,step) for(int j = (s); j < (e) ; j += step)
#define ex exit(0) 
#define sz(a) (a).size()
#define triple pair<pill, ll>
#define pinode pair<node*, node*>
#define quadra pair<pill, pill>
#define ld long double
using namespace std;
 
const ll N = 4e5 + 10;
const ll M = 1e3 + 10;
const ll big = 1e9;
const ll hsh2 = 1964325029;
const ll wp = 491;
const long long mod = 1e9 + 7;
const long double EPS = 1e-14;
const ll block = 1e7;
const ll shift = 2e3;
mt19937_64 rofl(chrono::steady_clock::now().time_since_epoch().count());

ll n, x[N], y[N];

vector<ll> z, z2;

ll f[N], k[N];
map<pill, ll> cnt;
int main() {
	speed;
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> x[i] >> y[i];
		z.pb(x[i]), z2.pb(y[i]);
	}
	sort(all(z)), sort(all(z2));
	z.erase(unique(all(z)), z.end()), z2.erase(unique(all(z2)), z2.end());
	for(int i = 1; i <= n; i++) {
    	x[i] = lower_bound(all(z), x[i]) - z.begin();
    	y[i] = lower_bound(all(z2), y[i]) - z2.begin();
		f[x[i]]++;
		k[y[i]]++;
		cnt[mp(x[i], y[i])]++;		
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++) {
    	ll b = cnt[mp(x[i], y[i])];
		ans += (f[x[i]] - b) * (k[y[i]] - b);
    }
    cout << ans;
}                     
/*
AAAACACA
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 10 ms 1388 KB Output is correct
13 Correct 10 ms 1516 KB Output is correct
14 Correct 14 ms 1516 KB Output is correct
15 Correct 224 ms 10328 KB Output is correct
16 Correct 222 ms 11096 KB Output is correct
17 Correct 217 ms 10328 KB Output is correct
18 Correct 245 ms 10328 KB Output is correct
19 Correct 825 ms 26948 KB Output is correct
20 Correct 592 ms 19824 KB Output is correct
21 Correct 796 ms 29112 KB Output is correct
22 Correct 779 ms 29124 KB Output is correct